Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
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
21 我的代码
#include#include int C,n,k,a[10];char chess[10][10];void dfs(int c,int r){ if(c==k+1 && r<=n+1) { C++; return; } if(r>n) return; int i,j; for(i=1;i<=n;i++) { int flg=1; if(chess[r][i]=='#') { for(j=1;j<=c-1;j++) { if(a[j]==i) flg=0; } if(flg){ a[c]=i; dfs(c+1,r+1); } } } dfs(c,r+1); return;}int main(){ int i,j; while(scanf("%d %d",&n,&k)!=EOF) { getchar(); if(n==-1 && k==-1) break; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%c",&chess[i][j]); } getchar(); } C=0; dfs(1,1); printf("%d\n",C); } return 0;}
#include#include using namespace std;int n, k, res;char m[10][10];bool vis[10][10];void dfs(int tx, int ty, int dep) { if (dep == k) { res ++; return ; } int i, j; for (i = tx; i < n; ++i) { for (j = (i==tx?ty:0); j < n; ++j) { if (!vis[i][j] && m[i][j] == '#') { bool vv[10][10]; memset(vv, 0, sizeof(vv)); for (int p = 0; p < n; ++p) { for (int q = 0; q < n; ++q) vv[p][q] = vis[p][q]; } for (int p = 0; p < n; ++p) { vis[i][p] = true; vis[p][j] = true; } dfs(i, j, dep+1); for (int p = 0; p < n; ++p) { for (int q = 0; q < n; ++q) vis[p][q] = vv[p][q]; } } } }}int main() { while(cin >> n >> k) { if (n==-1 && k==-1) break; memset(m, 0, sizeof(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> m[i][j]; } } res = 0; memset(vis, 0, sizeof(vis)); dfs(0,0,0); cout << res << endl; } return 0;}