Time Limit: 1000MS Memory Limit: 65536K
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。
代码 C++
1 #include <cstdio> 2 int n, k, data[100][2], id, opt; 3 bool inY[10], inX[10]; 4 void DFS(int now, int len){ 5 if (len == k){ ++opt; return; } 6 if (now >= id) return; 7 if (!(inY[data[now][0]] | inX[data[now][1]])){ 8 inY[data[now][0]] = inX[data[now][1]] = 1; 9 DFS(now + 1, len + 1); 10 inY[data[now][0]] = inX[data[now][1]] = 0; 11 } 12 DFS(now + 1, len); 13 } 14 int main(){ 15 int i, j; 16 char rd[10]; 17 while (scanf("%d%d ", &n, &k), n + k > 0){ 18 opt = id = 0; 19 for (i = 0; i < n; ++i){ 20 gets(rd); 21 for (j = 0; j < n; ++j){ 22 if (rd[j] == ‘#‘) data[id][0] = i, data[id][1] = j, ++id; 23 } 24 } 25 DFS(0, 0); 26 printf("%d\n", opt); 27 } 28 return 0; 29 }
原文：http://www.cnblogs.com/Simon-X/p/6286332.html