POJ 1321 棋盘问题 (DFS + 回溯)

题目链接：http://poj.org/problem?id=1321

题意：中文题目，就不多说了。。。。。。

思路：

　　解题方法挺多，刚开始想的是先从N行中选择出来含有“#”的K行，再在这K行中放置K个棋子，就好了。时间复杂度为O( C(n, k) * k! ),真实写的时候其实用了2^N * k!,勉强也过了。后面又想到可以先从第一个出现的“#”开始搜，搜完之后直接跳到下一行继续,就不用第一次做那么麻烦了。

代码：

（1）

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <stack>
 7 #include <queue>
 8 #include <vector>
 9 #include <algorithm>
10 #include <string>
11 
12 typedef long long LL;
13 using namespace std;
14 const int MAXN = 8;
15 int map[MAXN + 3][MAXN + 3];
16 int row[MAXN + 3];
17 int chose[MAXN + 3];
18 int n, k;
19 int ans;
20 
21 void chessDFS(int t) {
22     if(t > k) {
23         ++ans;
24     }
25     else {
26         int cnt = 0;
27         for(int i = 1; i <= n; i++) {//从1 ～ n 行找到放置第t个棋子所在的行。
28             if(chose[i]) ++cnt;
29             if(cnt == t && chose[i]) {
30                 for(int j = 1; j <= n; j++) {//在该行寻找“#”
31                     if(map[i][j] == '#' && row[j] == 0) {
32                         chose[i] = j; // 第t个棋子放在第 i行的第j个位置
33                         row[j] = 1;
34                         chessDFS(t + 1);
35                         row[j] = 0;
36                     }
37                 }
38             }
39         }
40     }
41 }
42 
43 int check(int k) {
44     for(int i = 1; i <= n; i++) {
45         if(map[k][i] == '#' && chose[k]) return 1;
46     }
47     return 0;
48 }
49 
50 void LineDFS(int t){
51     if(t > n){
52         int cnt = 0;
53         for(int i = 1; i <= n; i++) {
54             if(check(i)) cnt++;//判断chose数组中 1 的个数， 同时判断被选中行是否含有“#”，同时满足才算正真的选中
55         }
56         if(cnt == k) {//说明有K行被选中，且符合条件
57             memset(row, 0, sizeof(row));
58             chessDFS(1);//在这已经被选中的K行中放置K个棋子
59         }
60     }
61     else {
62         for(int i = 0; i < 2; i++) {//每行有两种状态，选和不选
63             chose[t] = i; //chose[t] = 1代表第t行被选则
64             LineDFS(t + 1);
65         }
66     }
67 }
68 
69 int main() {
70     while(scanf("%d%d", &n, &k) == 2 && (n != -1 && k != -1)) {
71         memset(map, '!', sizeof(map));
72         memset(row, 0, sizeof(row));
73         for(int i = 1; i <= n; i++) {
74             getchar();
75             for(int j = 1; j <= n; j++) {
76                 map[i][j] = getchar();
77             }
78         }
79         ans = 0;
80         LineDFS(1);//从N行中选择出来K行
81         printf("%d
", ans);
82     }
83     return 0;
84 }

(2)

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <stack>
 7 #include <queue>
 8 #include <vector>
 9 #include <algorithm>
10 #include <string>
11 
12 typedef long long LL;
13 using namespace std;
14 const int MAXN = 8;
15 int map[MAXN + 3][MAXN + 3];
16 int row[MAXN + 3];
17 int chose[MAXN + 3];
18 int n, k;
19 int ans;
20 
21 void DFS(int t, int line) {    
22     for(int i = 1; i <= n; i++) {
23         if(map[line][i] == '#' && !row[i]) {
24             row[i] = 1;
25             if(t == k) ++ans;
26             else {
27                 for(int j = line + 1; j <= n - (k - t) + 1; j++) {//第t+1个点从line+1行开始放
28                     DFS(t + 1, j);
29                 }
30             }
31             row[i] = 0;
32         }
33     }
34 }
35 
36 
37 int main() {
38     //freopen("input", "r", stdin);
39     //freopen("output", "w", stdout);
40     while(scanf("%d%d", &n, &k) == 2 && (n != -1 && k != -1)) {
41         memset(map, '!', sizeof(map));
42         memset(row, 0, sizeof(row));
43         for(int i = 1; i <= n; i++) {
44             getchar();
45             for(int j = 1; j <= n; j++) {
46                 map[i][j] = getchar();
47             }
48         }
49         ans = 0;
50         for(int i = 1; i <= n - k + 1; i++) DFS(1, i);//第一个点从第一行开始放    
51         printf("%d
", ans);
52     }
53     return 0;
54 }