POJ 1321 棋盘问题

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
", opt);
27     }
28     return 0;
29 }