3781 - 【START】2015暑期训练——2n皇后
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
题目输入
输入的第一行为一个整数M（0<M<10），代表测试数据组数
每组输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
题目输出
对应每组输入输出一个整数，表示总共有多少种放法。
输入/输出样例
题目输入
2 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
题目输出
2 0
C++解答
#include<iostream> #include<cstdio> using namespace std; const int maxn = 10; // 存储矩阵 int n; int tot = 0; // 统计解的个数 int site[maxn][maxn]; int W[maxn]; int B[maxn]; // 第i行黑皇后的位置 // 放黑皇后 void search_black(int cur) { if(cur == n) { tot++; } else for(int i = 0; i < n; i++) { // 也得确保没在此处放白皇后 if(W[cur] != i && site[cur][i]) { int ok = 1; B[cur] = i; for(int j = 0; j < cur; j++) { if(B[cur] == B[j] || cur-B[cur] == j-B[j] || cur+B[cur] == j+B[j]) { ok = 0; break; } } if(ok) search_black(cur+1); } } } // 放白皇后 void search_white(int cur) { if(cur == n) { search_black(0); } else for(int i = 0; i < n; i++) { if(site[cur][i]) { int ok = 1; W[cur] = i; for(int j = 0; j < cur; j++) { if(W[cur] == W[j] || cur-W[cur] == j-W[j] || cur+W[cur] == j+W[j]) { ok = 0; break; } } if(ok) search_white(cur+1); } } } int main() { //freopen("1.txt", "r", stdin); //freopen("2.txt", "w", stdout); int M; cin >> M; while(M--) { tot = 0; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> site[i][j]; } } search_white(0); cout << tot << endl; } return 0; }