总时间限制: 1000ms 内存限制: 65536kB 描述 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 输入 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 输出 对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。 样例输入
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1样例输出 2 1
分析：n皇后问题，不可以同行同列，那么每次递归都是增加一行确保不同行，然后设置一个一维数组作为列的标志，保证不同列。k个棋子，也就是k行，那么在主函数调用dfs的时候就要用for循环n-k遍。 dfs中遍历列，发现可以放置棋子的地方就判断还剩下几个棋子，如果只剩下一个就res++,然后返回，否则去设置列标志并且继续递归，递归的时候还是像主函数中设置for循环。
#include <iostream> using namespace std; //http://bailian.openjudge.cn/practice/1321/ //参考别人的才做出来，发现对dfs和bfs还需要练习 int n,k,c[10],res;//c[i]表示列是否被标记的情况 char a[10][10]; void dfs(int x,int y){ for(int i=0;i<n;i++){ //对每一列进行遍历 if(a[x][i]=='#'&&c[i]==0){ if(y==1){ res++; } else{ c[i]=1; for(int j=x+1;j<n-y+2;j++){ dfs(j,y-1); } c[i]=0; } } } } int main(int argc, char *argv[]) { while(cin>>n>>k){ if(n==-1&&k==-1){ break; } res=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } c[i]=0; } for(int i=0;i<=n-k;i++){ //放置k个棋子最少需要k行，这样满足不同行的要求 dfs(i,k); } cout<<res<<endl; } return 0; }