随笔-28  评论-51  文章-10  trackbacks-0

#include <stdio.h>
#include 
<stdlib.h>
void  eightQueen(int** board, int n, int m);
/*if valid, return 1*/
int isValid(int**  board,int n, int m, int i, int j);

int main()
{
    
int **board = (int **)malloc(sizeof(int *)*4);
    
int i = 0, j=0;
    
for(;i<4; i++)
    {
        board[i] 
= (int *) malloc(sizeof(int* 4);
    }
     i 
= 0;
     j 
= 0;
    
for(;i<4; i++)
        
for(; j < 4; j++)
        {
            board[i][j] 
= 0;
        }    
    eightQueen(board, 
4,4);
    
     i 
= 0, j = 0;
     
for(; i<4; i++)
     {
        
for(; j < 4; j++)
        {
            printf(
"%d(%d) ",board[i][j], i);
            
        }    
    }
        
    
return 0;
}


void  eightQueen(int** board, int n, int m)
{    
int ii = 0;
    
int jj =0;
    
int k = 0;
    
while(ii < n && ii >= 0)
    {
    
        
        jj 
= 0;
        
while( jj<m)
        {
            
if(board[ii][jj] == 1 && jj+1 < m)
            {
                board[ii][jj] 
= 0;
                board[ii][
++jj] = 1;
            }
            
else
                board[ii][jj] 
= 1;
            
            
if(isValid(board, n,m,ii,jj))
            {
                
if(ii == n-1return;
            }
             
else
             {
                 ii
++;
                   
break;
              }    
              jj
++;
        }
        
if(jj>=m)
        {
            board[ii][jj
-1= 0;
            ii
--;
        }
        
    }
    
}
int isValid(int** board,int n, int m, int i, int j)
{
    
//判断是否同列
    int temp = 0;
    
for(; temp < n; temp++)
    {
        
if(temp != i)
        {
        
if(board[temp][j] != 0)
            
return 0;
        }
            
    }
    
//判断是否右上角
    int ii, jj;
    
for(ii =i-1, jj=j+1; ii >=0&&jj <= m; ii--,jj++)//注意中间判断条件的&&
    {
        
if(board[ii][jj] != 0)
            
return 0;
    }
    
//判断是否左上角
    for(ii =i- 1,jj=j-1; ii >=0&&jj >=0;ii--,jj--)
    {
        
if(board[ii][jj] != 0)
            
return 0;
    }
    
return 1;

    
}




posted on 2008-04-12 23:39 fullfocus 阅读(185) 评论(0)  编辑  收藏 所属分类: 算法

只有注册用户登录后才能发表评论。


网站导航: