問題描述
給定一個(gè)n*n的棋盤娄帖，棋盤中有一些位置不能放皇后。現(xiàn)在要向棋盤中放入n個(gè)黑皇后和n個(gè)白皇后，使任意的兩個(gè)黑皇后都不在同一行挠说、同一列或同一條對(duì)角線上，任意的兩個(gè)白皇后都不在同一行愿题、同一列或同一條對(duì)角線上损俭。問總共有多少種放法蛙奖？n小于等于8。
輸入格式
輸入的第一行為一個(gè)整數(shù)n撩炊，表示棋盤的大小外永。
接下來n行，每行n個(gè)0或1的整數(shù)拧咳，如果一個(gè)整數(shù)為1伯顶，表示對(duì)應(yīng)的位置可以放皇后，如果一個(gè)整數(shù)為0骆膝，表示對(duì)應(yīng)的位置不可以放皇后祭衩。
輸出格式
輸出一個(gè)整數(shù)，表示總共有多少種放法阅签。
樣例輸入
4
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
n皇后問題的變形, 思路是先放白皇后, 將白皇后放完之后, 在往上放置黑皇后
#include <bits/stdc++.h>
using namespace std;
int n;
int m[9][9];
int blackPos[9];
int whitePos[9];
int cnt = 0;
// 判斷當(dāng)前能否放置皇后
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;
}
// 對(duì)黑皇后的放置進(jìn)行深搜
void blackDfs(int row) {
if(row == n) {
// 如果已經(jīng)放置完成了n個(gè)黑皇后, 那么擺放的方法加1
cnt++;
return ;
} else {
for(blackPos[row] = 0; blackPos[row] < n; blackPos[row]++) {
// 如果當(dāng)前位置沒有與其他黑皇后發(fā)生沖突, 當(dāng)前可以放置黑皇后而且當(dāng)前的位置沒有放置白皇后
if(isSafe(blackPos, row) && m[row][blackPos[row]] == 1 & blackPos[row] != whitePos[row]) {
blackDfs(row+1);
}
}
}
}
// 對(duì)白皇后的放置進(jìn)行深搜
void whiteDfs(int row) {
if(row == n) {
// 如果已經(jīng)放置完成了n個(gè)白皇后, 則進(jìn)行放置黑皇后
blackDfs(0);
return;
} else {
for(whitePos[row] = 0; whitePos[row] < n; whitePos[row]++) {
// 當(dāng)前位置沒有與其他白皇后沖突且當(dāng)前位置能放置
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);
//blackDfs(0);
printf("%d\n", cnt);
return 0;
}
