问题： 给定一个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 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
样例输出
0
分析：1.用一个二维数组构造出一个n*n的矩阵。
2.逐行选择某个合适的坐标来放置所谓的黑或者白皇后（如果放了黑，下次就放白的）。
3.接着步骤2，放另一种皇后。
步骤二和步骤三的实现：
1 void dfs(int i,int q)//i是初始行 q指的是是否在某位置上放置皇后 2 { 3 for(int j=0;j<n;j++) 4 { 5 //不能放的或者已经放过的 6 if(s[i][j]==0||s[i][j]==2)//已经放过的是2 7 { 8 continue; 9 } 10 int flag=1;//默认可以放 11 int y1=j-1;//左上角的黑皇后 12 int y2=j+1;//右上角的黑皇后 13 for(int l=i-1;l>=0;l--) 14 { 15 //判断同一列、斜线上是否有相同皇后（同行肯定不会有：从上到下进行的） 16 //同一列 17 if(s[l][j]==q)//判断同一列上是否有相同的皇后 18 { 19 flag=0; 20 break; 21 } 22 //斜线 23 if(y1>=0&&s[l][y1]==q)//判断左对角线上是否有 24 { 25 flag=0; 26 break; 27 } 28 y1--; 29 if(y2<n&&s[l][y2]==q) 30 { 31 flag=0; 32 break; 33 } 34 y2++; 35 } 36 if(flag) 37 { 38 s[i][j]=q;//放皇后 39 if(i<n-1) 40 { 41 dfs(i+1,q); 42 } 43 else 44 { 45 //黑皇后放完了，开始放白皇后； 46 //白皇后放完的话就是一种方法结束 47 if(q==2) 48 { 49 dfs(0,3); 50 } 51 else 52 { 53 count++; 54 } 55 } 56 s[i][j]=1;//复原开始下一次 57 } 58 } 59 }
现在用C来实现
（其实用啥都一样，我不是太会用C++）
1 #include <stdio.h> 2 void dfs(int i,int q); 3 int s[13][13]; 4 int n,count=0; 5 int main(){ 6 scanf("%d",&n); 7 for(int i=0;i<n;i++) 8 { 9 for(int j=0;j<n;j++) 10 { 11 scanf("%d",&s[i][j]);//对矩阵赋值 12 } 13 } 14 dfs(0,2);//黑皇后 15 printf("%d",count); 16 return 0; 17 } 18 void dfs(int i,int q)//i=0 q=2 19 { 20 for(int j=0;j<n;j++) 21 { 22 //不能放的或者已经放过的 23 if(s[i][j]==0||s[i][j]==2)//已经放过的是2 24 { 25 continue; 26 } 27 int flag=1;//默认可以放 28 int y1=j-1;//左上角的黑皇后 29 int y2=j+1;//右上角的黑皇后 30 for(int l=i-1;l>=0;l--) 31 { 32 //判断同一列、斜线上是否有相同皇后（同行肯定不会有：从上到下进行的） 33 //同一列 34 if(s[l][j]==q)//判断同一列上是否有相同的皇后 35 { 36 flag=0; 37 break; 38 } 39 //斜线 40 if(y1>=0&&s[l][y1]==q)//判断左对角线上是否有 41 { 42 flag=0; 43 break; 44 } 45 y1--; 46 if(y2<n&&s[l][y2]==q) 47 { 48 flag=0; 49 break; 50 } 51 y2++; 52 } 53 if(flag) 54 { 55 s[i][j]=q;//放皇后 56 if(i<n-1) 57 { 58 dfs(i+1,q); 59 } 60 else 61 { 62 //黑皇后放完了，开始放白皇后； 63 //白皇后放完的话就是一种方法结束 64 if(q==2) 65 { 66 dfs(0,3); 67 } 68 else 69 { 70 count++; 71 } 72 } 73 s[i][j]=1;//复原开始下一次 74 } 75 } 76 }
下面是不正宗的C++
#include<iostream> using namespace std; int s[13][13]; int n; int count=0;//计数 void dfs(int i,int q)//i=0 q=2 { for(int j=0;j<n;j++) { //不能放的或者已经放过的 if(s[i][j]==0||s[i][j]==2)//已经放过的是2 { continue; } int flag=1;//默认可以放 int y1=j-1;//左上角的黑皇后 int y2=j+1;//右上角的黑皇后 for(int l=i-1;l>=0;l--) { //判断同一列、斜线上是否有相同皇后（同行肯定不会有：从上到下进行的） //同一列 if(s[l][j]==q)//判断同一列上是否有相同的皇后 { flag=0; break; } //斜线 if(y1>=0&&s[l][y1]==q)//判断左对角线上是否有 { flag=0; break; } y1--; if(y2<n&&s[l][y2]==q) { flag=0; break; } y2++; } if(flag) { s[i][j]=q;//放皇后 if(i<n-1) { dfs(i+1,q); } else { //黑皇后放完了，开始放白皇后； //白皇后放完的话就是一种方法结束 if(q==2) { dfs(0,3); } else { count++; } } s[i][j]=1;//复原开始下一次 } } } int main() { cin>>n;//对n赋值 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>s[i][j];//对矩阵赋值 } } dfs(0,2);//黑皇后 cout<<count<<endl; return 0; }
结尾了，，有什么不懂的私聊我，一起学习，一起进步。1186294207
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
