题目:
接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
#include <stdio.h>
#define N 8
int n = 0 ;
int f[N][N] = {0};
int sum = 0;
int flag = 0;
/*同一行、同一列、对角线 为 0*/
void change(int i , int j , int k , int num[][N])
{
int tmp = 0 ;
int x = 0 , y = 0 ;
/*由于是从上至下搜索,可以考虑删去对上面的处理*/
//N = 5;
//int arr[N][2] = {{0,-1},{0,1},{1,-1},{1,0},{1,1},};
int arr[N][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1},};
for (tmp = 0 ; tmp < N ; tmp ++)
{
x = i + arr[tmp][0] ;
y = j + arr[tmp][1] ;
while(x >= 0 && y >= 0 && x < n && y < n)
{
num[x][y] = k;
x += arr[tmp][0];
y += arr[tmp][1];
}
}
return ;
}
void dfs_2n(int step , int map[][N])
{
int x = 0 , y = 0 ;
int i = 0 , j = 0 , k = 0 ;
int tmp[N][N] = {0};
if (step == n )
{
sum ++;
#if 0/*打印棋盘.黑皇后->2,白皇后->3*/
printf("====================\n");
for (x = 0 ; x < n ; x ++)
{
for (y = 0 ; y < n ; y ++)
printf("%d ",f[x][y]);
printf("\n");
}
#endif
return ;
}
for (j = 0 ; j < n ; j ++)
{
if (map[step][j])
{
map[step][j] = 0;
f[step][j] = 3; /*白皇后->3*/
for (x = 0 ; x < n ; x ++)
{
for (y = 0 ; y < n ; y ++)
{
tmp[x][y] = map[x][y];
}
}
change(step,j,0,tmp);
dfs_2n( step+1 , tmp);
map[step][j] = 1;
f[step][j] = 1;
}
}
return ;
}
void dfs_1n(int step , int map[][N])
{
int x = 0 , y = 0 ;
int i = 0 , j = 0 ;
int tmp[N][N] = {0};
if (step == n )
{
for (i = 0 ; i < n ; i ++)
{
for (j = 0 ; j < n ; j ++)
{
if (f[i][j] == 1)
map[i][j] = 1;
else
map[i][j] = 0;
}
}
dfs_2n( step%n , map);
return ;
}
for (j = 0 ; j < n ; j ++)
{
if (map[step][j])
{
map[step][j] = 0;
f[step][j] = 2;/*黑皇后->2*/
for (x = 0 ; x < n ; x ++)
{
for (y = 0 ; y < n ; y ++)
{
tmp[x][y] = map[x][y];
}
}
change(step,j,0,tmp);
dfs_1n( step+1 , tmp);
map[step][j] = 1;
f[step][j] = 1;
}
}
return ;
}
int main(void)
{
int i = 0 , j = 0 ;
int map[N][N] = {0};
scanf("%d",&n);
for (i = 0 ; i < n ; i ++)
{
for (j = 0 ; j < n ; j ++)
{
scanf("%d",&map[i][j]);
f[i][j] = map[i][j];
}
}
dfs_1n(0,map);
printf("%d",sum);
return 0;
}