Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。  每组数据的第一行是两个正整数，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 总结： 简单的dfs，但是在动手写代码之前还是要搞清楚如何dfs边界在哪里，怎么剪枝等问题，要不然DeBUg会烦死人的！还有，用scanf来读入的时候已定要小心各种空格和回车，不然容易出问题 #include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn=10; int n,map[maxn][maxn],vis[maxn],ans,tot; void dfs(int k,int num) { if(k>n||num==0||n-k+1<num) return; for(int i=0;i<=n;i++) { if(i==0) dfs(k+1,num); else if(map[k][i]==1&&vis[i]==0) { vis[i]=1; if(num-1==0) ans++; else dfs(k+1,num-1); vis[i]=0; } } } int main() { //freopen("/Users/zhangjiatao/Documents/暑期训练/input.txt","r",stdin); while(scanf("%d%d",&n,&tot)==2) { getchar(); //cout<<n<<endl; if(n==-1) break; ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { char temp; scanf("%c",&temp); //cin>>temp; if(temp=='#') map[i][j]=1; else map[i][j]=0; } getchar(); } // for(int i=1;i<=n;i++) // { // for(int j=1;j<=n;j++) // { // cout<<map[i][j]<<" "; // } // cout<<endl; // } for(int i=1;i<=n;i++) memset(vis,0,sizeof(vis)); dfs(1,tot); printf("%d\n",ans); } return 0; }