- 总时间限制:
- 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
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #include <algorithm> 6 #include <set> 7 #include <queue> 8 #include <stack> 9 10 using namespace std; 11 char map[10][10]; 12 int vis[10];//第i列是否放置了棋子 13 int cnt;//已放棋子的数目 14 int sum;//放置方法的总数 15 int n,k; 16 void dfs(int s) 17 { 18 int i; 19 if(cnt==k){//所有的棋子都放置好 20 sum++; 21 return ; 22 } 23 else{ 24 if(s>=n)//如果越界 25 return ;//返回 26 else{ 27 for(i=0;i<n;i++){//讲一个棋子尝试放在0-n-1列的某一行 28 if(map[s][i]=='#'&&!vis[i]){ 29 vis[i]=1;//标记该列已经放了棋子 30 cnt++;//棋子数+1 31 dfs(s+1);//继续搜索 32 cnt--;//经过一轮递归后num始终保持不变,因为没有放棋子 33 vis[i]=0;//在此处不放棋子 34 } 35 } 36 dfs(s+1);//进行剩下的k-1个棋子的遍历 37 } 38 } 39 } 40 int main() 41 { 42 int i; 43 while(~scanf("%d %d",&n,&k)){ 44 getchar(); 45 if(n==-1&&k==-1) break; 46 memset(vis,0,sizeof(vis)); 47 for(i=0;i<n;i++) 48 scanf("%s",map[i]); 49 cnt=sum=0; 50 dfs(0); 51 printf("%d\n",sum); 52 } 53 return 0; 54 }
参考： http://blog.csdn.net/u013486414/article/details/43878071
