POJ - 1321 棋盘问题 （DFS递归）

在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放k个棋子的所有可行的摆放方案C。Input输入含有多组测试数据。每组数据的第一行是两个正整数n k用一个空格隔开表示了将在一个n*n的矩阵内描述棋盘以及摆放棋子的数目。 n 8 , k n当为 -1 -1 时表示输入结束。随后的n行描述了棋盘的形状每行有n个字符其中 # 表示棋盘区域 . 表示空白区域数据保证不出现多余的空白行或者空白列。Output对于每一组数据给出一行输出输出摆放的方案数目C 数据保证C2^31。Sample Input2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1Sample Output2 1层层递归#includeiostream #includecstring using namespace std; char c[10][10]; int flag[10]; long long ans; int n,k,m; void dfs(int y) { if(mk) { ans; return ; } if(yn) return ; for(int i1; in; i) //遍历一行 { if(!flag[i]c[y][i]#) //由于不能在同列可用一维数组记录该列是否有棋子 { flag[i]1; m; dfs(y1); //该位置标记过了再去遍历后面的 flag[i]0; //取消标记该位置 m--; } } dfs(y1); //跳转到下一层 } int main() { while(cinnk) { if(n-1k-1) break; memset(flag,0,sizeof(flag)); for(int i1; in; i) { for(int j1; jn; j) { cinc[i][j]; } } ans0,m0; dfs(1); coutansendl; } return 0; }