资源限制
时间限制:1.0s 内存限制:512.0MB
问题描述
给定一个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
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 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
代码
1 #include<iostream> 2 #include<cmath> 3 #include<cstring> 4 using namespace std; 5 6 //思路: 先对黑皇后进行安放,并记录下所有可能的方法(用二维数组存) 7 //对于每种已经能放好的黑皇后方法,将黑皇后的位置设为0表示能不能放, 8 //再去看白皇后有多少种安方法,最后加起来即可 9 //并且搜黑皇后和搜白皇后其实可以用同一个函数(稍微有些区别,也可以分开更清晰) 10 int n=0; 11 int time=0; 12 int map[10][10]={0}; 13 int temp[10][10]={0}; //临时地图 14 int t=0; //用于记录存放了多少种安置和黑皇的方法 15 int cun[1000][9]={0}; //cun[i][j]中,i代表第i种黑皇后放置方法(i从0开始),j代表第j行,cun[1000][8]代表第i种方法中第j行第cun[1000][8]列(存放黑皇) 16 int queenpos[10]={0}; 17 int pos[10]={0}; 18 void queen(int k); 19 void Bqueen(int k); 20 int main(){ 21 cin>>n; 22 for(int i=1;i<=n;i++){ 23 for(int j=1;j<=n;j++){ 24 cin>>map[i][j]; 25 } 26 } 27 28 //先对黑皇位置搜索 29 queen(1); //第1行开始 30 if(t==0){ 31 cout<<"0"; 32 return 0; 33 } 34 35 int sum=0; 36 for(int i=0;i<t;i++){ 37 time=0; 38 memcpy(temp,map,sizeof(map)); //把map值赋值给temp 39 for(int m=1;m<=n;m++){ 40 temp[m][cun[i][m]]=0; //表示这个位置被黑占用了 41 } 42 Bqueen(1); //白皇后开始搜索 43 sum+=time; 44 } 45 cout<<sum; 46 return 0; 47 } 48 void queen(int k){ 49 if(k==n+1){ //表示前k行都已经安放好了皇后 50 for(int i=1;i<=n;i++){ 51 cun[t][i]=queenpos[i]; 52 } 53 t++; 54 return; 55 } 56 57 for(int i=1;i<=n;i++){ //现在处于第k行,对于i列位置进行选择 58 int j=1; 59 for(j=1;j<k;j++){ 60 if(queenpos[j]==i||abs(queenpos[j]-i)==abs(k-j)){ 61 break; //表示存在冲突 62 } 63 } 64 if(k==j&&map[k][i]==1){ 65 queenpos[k]=i; 66 queen(k+1); 67 } 68 } 69 } 70 71 void Bqueen(int k){ 72 if(k==n+1){ //表示前k行都已经安放好了皇后 73 time++; 74 return ; 75 } 76 77 for(int i=1;i<=n;i++){ //现在处于第k行,对于i列位置进行选择 78 int j=1; 79 for(j=1;j<k;j++){ 80 if(pos[j]==i||abs(pos[j]-i)==abs(k-j)){ 81 break; //表示存在冲突 82 } 83 } 84 if(k==j&&temp[k][i]==1){ 85 pos[k]=i; 86 Bqueen(k+1); 87 } 88 } 89 }