【HDOJ】1045 Fire Net

经典深搜。注意满足条件。
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAXNUM 5
 5 
 6 char map[MAXNUM][MAXNUM];
 7 int visit[MAXNUM][MAXNUM];
 8 
 9 int chk(int row, int col, int n) {
10     int i, k;
11 
12     if (row<0 || row>=n || col<0 || col>=n )
13         return 0;
14     if (visit[row][col] || map[row][col]!='.')
15         return 0;
16 
17     // if this position is valid or not
18     k = 0;
19     for (i=col-1; i>=0; --i) {
20         if (map[row][i] == 'X')
21             break;
22         if (map[row][i] == '.' && visit[row][i]) {
23             k = 1;
24             break;
25         }
26     }
27     if (k) return 0;
28 
29     for (i=col+1; i<n; ++i) {
30         if (map[row][i] == 'X')
31             break;
32         if (map[row][i] == '.' && visit[row][i]) {
33             k = 1;
34             break;
35         }
36     }
37     if (k) return 0;
38 
39     for (i=row-1; i>=0; --i) {
40         if (map[i][col] == 'X')
41             break;
42         if (map[i][col] == '.' && visit[i][col]) {
43             k = 1;
44             break;
45         }
46     }
47     if (k) return 0;
48 
49     for (i=row+1; i<n; ++i) {
50         if (map[i][col] == 'X')
51             break;
52         if (map[i][col] == '.' && visit[i][col]) {
53             k = 1;
54             break;
55         }
56     }
57 
58     if (k)
59         return 0;
60     else
61         return 1;
62 }
63 
64 int dfs(int n) {
65     int i, j, tmp, max = 0;
66 
67     for (i=0; i<n; ++i) {
68         for (j=0; j<n; ++j) {
69             if ( chk(i, j, n) ) {
70                 visit[i][j] = 1;
71                 tmp = dfs(n) + 1;
72                 if (tmp > max)
73                     max = tmp;
74                 visit[i][j] = 0;
75             }
76         }
77     }
78 
79     return max;
80 }
81 
82 int main() {
83     int n, amount;
84     int i;
85 
86     while (scanf("%d", &n)!=EOF && n) {
87         getchar();
88         for (i=0; i<n; ++i)
89             gets(map[i]);
90 
91         memset(visit, 0, sizeof(visit));
92         amount = dfs(n);
93         printf("%d
", amount);
94     }
95 
96     return 0;
97 }