BASIC-27_蓝桥杯_2n皇后问题

题目:

问题描述

　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式

　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出格式

　　输出一个整数，表示总共有多少种放法。

样例输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

2

样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

 

思路:

1:先列出黑皇后的情况，再进入至白皇后的搜索(黑、白皇后分开写，便于回溯);

2:之前一直会出错是由于黑白皇后都在一个函数中递归，条件没设置好(烦)，导致在回溯失败;

 

示例代码:

#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;
}