You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
70 lines
1.4 KiB
70 lines
1.4 KiB
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
//题的变形, 思路是先放白皇后, 将白皇后放完之后, 在往上放置黑皇后
|
|
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
int n;
|
|
int m[9][9];
|
|
int blackPos[9];
|
|
int whitePos[9];
|
|
int cnt = 0;
|
|
|
|
// 判断当前能否放置皇后
|
|
bool isSafe(int pos[], int row) {
|
|
for(int i = 0; i < row; i++) {
|
|
if(pos[i] == pos[row] || abs(pos[i] - pos[row]) == abs(i - row)) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// 对黑皇后的放置进行深搜
|
|
void blackDfs(int row) {
|
|
if(row == n) {
|
|
// 如果已经放置完成了n个黑皇后, 那么摆放的方法加1
|
|
cnt++;
|
|
return ;
|
|
} else {
|
|
for(blackPos[row] = 0; blackPos[row] < n; blackPos[row]++) {
|
|
// 如果当前位置没有与其他黑皇后发生冲突, 当前可以放置黑皇后而且当前的位置没有放置白皇后
|
|
if(isSafe(blackPos, row) && m[row][blackPos[row]] == 1 & blackPos[row] != whitePos[row]) {
|
|
blackDfs(row+1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// 对白皇后的放置进行深搜
|
|
void whiteDfs(int row) {
|
|
if(row == n) {
|
|
// 如果已经放置完成了n个白皇后, 则进行放置黑皇后
|
|
blackDfs(0);
|
|
return;
|
|
} else {
|
|
for(whitePos[row] = 0; whitePos[row] < n; whitePos[row]++) {
|
|
// 当前位置没有与其他白皇后冲突且当前位置能放置
|
|
if(isSafe(whitePos, row) && m[row][whitePos[row]] == 1) {
|
|
whiteDfs(row+1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
int main() {
|
|
scanf("%d", &n);
|
|
for(int i = 0; i < n; i++) {
|
|
for(int j = 0; j < n; j++) {
|
|
scanf("%d", &m[i][j]);
|
|
}
|
|
}
|
|
whiteDfs(0);
|
|
printf("%d\n", cnt);
|
|
|
|
return 0;
|
|
}
|
|
|
|
|