<题目链接>
题目描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
解题分析：
此题与n皇后问题十分类似，也是利用递归回溯求解，因为每行只能放一个白皇后，所以可以用一维数组记录皇后所放的位置，如 qw[x]=i，表明白皇后放在第x行第i列（黑皇后类似）。这题放2n个皇后，我采取的做法是，先放n个黑皇后，再放n个白皇后，具体实现见代码，一些细节方面我都标注出来了，并且做了详细解释。
#include <cstdio>
#include <cstring>
#include <cmath> #define clr(a,b) memset(a,b,sizeof(a))
int n,ans;
int map[][];
int qw[],qb[]; //白、黑皇后对应行所在的列数
int vis[][];
bool juge(int x,int cal[]){
if(!map[x][cal[x]]||vis[x][cal[x]])return false; //如果该点为0或者已经有皇后，则不能放
for(int i=;i<x;i++){
if(cal[i]==cal[x]||(abs(i-x)==abs(cal[i]-cal[x])))return false; //与之前放的同色皇后不在同一列，不在同一对角线
}
return true;
}
void init(){
ans=;
clr(vis,);clr(qw,);clr(qb,);
}
void dfs_w(int x){ //放白皇后
if(x==n+){
ans++;
return;
}
for(int i=;i<=n;i++){
qw[x]=i;
if(juge(x,qw)){
vis[x][i]=;
dfs_w(x+);
vis[x][i]=;
}
}
}
void dfs_b(int x){ //放黑皇后
if(x==n+){ //这里只用判断是不是到达第n+1行就能判断是否放了n个黑皇后，不用另外用一个变量记录放的黑皇后的数量
dfs_w(); //因为如果某一行没有放黑皇后，那么它根本就不能够向下一行搜索
return;
}
for(int i=;i<=n;i++){
qb[x]=i; //这里先放皇后再判断也是没问题的，因为如果放了皇后之后，发现不符合，这也没关系，因为qb[x]的值会被下一个循环
if(juge(x,qb)){ //的i值所覆盖。即使是循环的最后一个值不符合也没有关系，因为如果循环最后一个i不符合的话，那么它根本不会向下递归
vis[x][i]=; //也就自然不会对结果造成影响
dfs_b(x+);
vis[x][i]=;
}
}
}
int main(){
init();
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&map[i][j]);
dfs_b();
printf("%d\n",ans);
return ;
}
2018-08-26