Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
Sample Output
2 1
#include <set> //本意是用set检查是否冲突，结果用set会超时
#include <cstdio>
using namespace std;
int rows[9];//check collision
int cols[9];//check collision
int top = 0;//pointer to rows, cols
char board[9][9];//棋盘
int pos_sum[9][9];//从board[0][0]到board[i][j]累计'#'数
int n, k;//n*n棋盘，放k个棋子
int cnt;//方案数
int total = 0;//棋盘上#的总个数
bool exist(int row, int col){//检查是否冲突，冲突返回true
for(int i = 0; i < top; i++){
if(rows[i] == row || cols[i] == col){
return true;
}
}
return false;
}
void put(int row, int col, int k){//try to put k chesses from board[row][col]
if(k == 0){
cnt++;
return;
}
if(total - pos_sum[row][col] + 1 < k || n - row < k){//剪枝
return;
}
for(int i = row; i < n; i++){
for(int j = ((i == row)?col:0); j < n; j++){//这个地方意思是对row这行，从col列开始遍历，对之后的行，从第0列开始遍历。也可以写成两个循环，不过那样又太麻烦，没想到特别好的写法
//开始在这里犯了一个严重的错误:
//for(int i = row...)
// for(int j = col...)
// 这个是检查右下角的矩阵！而不是从这个点开始的所有点！！
if(board[i][j] == '#' && !exist(i, j)){
rows[top] = i;
cols[top] = j;
top++;
if(j + 1 <= n - 1){
put(i, j + 1, k - 1);
}else if(i + 1 <= n - 1){
put(i + 1, 0, k - 1);
}else if(k - 1 == 0){//没位置了，同时也放完了
cnt++;
}
top--;
}
}
}
}
int main()
{
while(scanf("%d%d", &n, &k) != EOF && n != -1){
cnt = 0;
for(int i = 0; i < n; i++){
scanf("%s", board[i]);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == '#'){
pos_sum[i][j] = total + 1;
total++;
}
}
}
put(0,0,k);
printf("%d\n", cnt);
}
return 0;
}
这个代码风格也是挺糟糕的，到处是全局变量，不过这样程序写起来很方便
改进：
#include <set> #include <cstdio> using namespace std; int rows[9];//check collision int cols[9]; int top = 0;//pointer to rows, cols char board[9][9]; int pos_sum[9][9]; int n, k; int cnt; int total = 0; bool exist(int row, int col){//检查是否冲突，冲突返回true for(int i = 0; i < top; i++){ if(rows[i] == row || cols[i] == col){ return true; } } return false; } void put(int row, int k){//try to put k chesses from board[row][0] if(k == 0){ cnt++; return; } //k > 0 if(n - row < k || total - pos_sum[row][0] + 1 < k){//剪枝 return; } for(int i = row; i < n; i++){ for(int j = 0; j < n; j++){ if(board[i][j] == '#' && !exist(i, j)){ rows[top] = i; cols[top] = j; top++; //本行不会再放，一定是从下一行放 put(i + 1, k - 1);//i + 1 >= n is also ok top--; } } } } int main() { while(scanf("%d%d", &n, &k) != EOF && n != -1){ cnt = 0; for(int i = 0; i < n; i++){ scanf("%s", board[i]); } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(board[i][j] == '#'){ pos_sum[i][j] = total + 1; total++; } } } put(0,k); printf("%d\n", cnt); } return 0; }