给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。
现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。
问总共有多少种放法？
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
n小于等于8。
输出一个整数，表示总共有多少种放法。
4 1111 1111 1111 1111 4 1011 1111 1111 1111 样例输出 2 0
探讨2n皇后问题之前，先看看N皇后问题 用vis[3][] 标记已经访问过的纵，和两个对角线。这样复杂度就可以大大减低o(1)的时间内可以判定是否可行。
对于纵排是否可以访问只要记录那一纵的横坐标即可；对角线是直线，我们记录他的截距即可。
说了这么多，为什么我没提到横排的问题，这个自己体会代码吧，懒得打字了。
#include<stdio.h>#include<string.h>#define MAX_N 8bool map[MAX_N][MAX_N];bool vis[3][MAX_N*2];int N,ans;void dfs_1(int cnt){ if(cnt==N){ans++;return ;} for(int i=0;i<N;i++){ if(vis[0][i]||vis[1][i+cnt]||vis[2][N-cnt+i]) continue; vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=true; dfs_1(cnt+1); vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=false; }}int main(){ while(~scanf("%d",&N)){ for(int j=0;j<N;j++) for(int k=0;k<N;k++) scanf("%1d",&map[k][j]); ans=0; dfs_1(0); PRintf("%d/n",ans); } return 0;}在上面基础上dfs再走一遍就解决2n皇后问题了 //我把bool型的map写成char，因为这个WA了两次，，，我也不知道原因，理论上是没问题的，不知道是oj的问题还是数据的问题
#include<stdio.h>#include<string.h>#define MAX_N 20char map[MAX_N][MAX_N];bool vis[3][MAX_N*2];bool vis_0[3][MAX_N*2];bool used[MAX_N][MAX_N];int N,ans;void dfs_0(int cnt){ if(cnt==N){ans++;return ;} for(int i=0;i<N;i++){ if(vis_0[0][i]||vis_0[1][i+cnt]||vis_0[2][N-cnt+i]||used[cnt][i]||map[cnt][i]=='0') continue; vis_0[0][i]=vis_0[1][i+cnt]=vis_0[2][N-cnt+i]=true; dfs_0(cnt+1); vis_0[0][i]=vis_0[1][i+cnt]=vis_0[2][N-cnt+i]=false; }}void dfs_1(int cnt){ if(cnt==N){ dfs_0(0); return ;} for(int i=0;i<N;i++){ if(vis[0][i]||vis[1][i+cnt]||vis[2][N-cnt+i]||map[cnt][i]=='0') continue; used[cnt][i]=vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=true; dfs_1(cnt+1); used[cnt][i]=vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=false; }}int main(){ while(~scanf("%d",&N)){ for(int j=0;j<N;j++) scanf("%s",map[j]); memset(vis,0,sizeof(vis)); memset(vis_0,0,sizeof(vis_0)); memset(used,0,sizeof(used)); ans=0; dfs_1(0); printf("%d/n",ans); } return 0;}新闻热点
疑难解答
