【HDOJ】1983 Kaitou Kid

不仅仅是DFS，还需要考虑可以走到终点。同时，需要进行预处理。至多封闭点数为起点和终点的非墙壁点的最小值。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <queue>
  6 using namespace std;
  7 
  8 typedef struct node_st {
  9     int x, y, t, flg;
 10     node_st() {}
 11     node_st(int xx, int yy, int tt, int fflg) {
 12         x=xx; y=yy; t=tt; flg=fflg;
 13     }
 14 } node_st;
 15 
 16 char map[10][10];
 17 char visit[10][10][2];
 18 int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
 19 int n, m, time, fmin;
 20 int begx, begy, endx, endy;
 21 
 22 bool check(int x, int y) {
 23     if (x<0 || x>=n || y<0 || y>= m)
 24         return false;
 25     return true;
 26 }
 27 
 28 bool bfs() {
 29     queue<node_st> que;
 30     int x, y, t, flg;
 31     int i;
 32     node_st node;
 33 
 34     memset(visit, 0, sizeof(visit));
 35     que.push(node_st(begx, begy, 0, 0));
 36     visit[begx][begy][0] = 1;
 37 
 38     while ( !que.empty() ) {
 39         node = que.front();
 40         que.pop();
 41         t = node.t;
 42         if (t == time)
 43             break;
 44         for (i=0; i<4; ++i) {
 45             x = node.x + direct[i][0];
 46             y = node.y + direct[i][1];
 47             flg = node.flg;
 48             if ( !check(x, y) )
 49                 continue;
 50             if (map[x][y] != '#') {
 51                 if (map[x][y] == 'E' && flg==1)
 52                     return true;
 53                 if (map[x][y] == 'J')
 54                     flg = 1;
 55                 if (t<time && !visit[x][y][flg]) {
 56                     visit[x][y][flg] = 1;
 57                     que.push(node_st(x, y, t+1, flg));
 58                 }
 59             }
 60         }
 61     }
 62 
 63     return false;
 64 }
 65 
 66 void printmap() {
 67     for (int i=0; i<n; ++i)
 68         printf("	%s
", map[i]);
 69 }
 70 
 71 int dfs(int t, int cur) {
 72     int flg = 0;
 73     char ch;
 74 
 75     if (t >= fmin)
 76         return 0;
 77 
 78     for (int i=0; i<n; ++i) {
 79         for (int j=0; j<m; ++j) {
 80             if (map[i][j]=='.' || map[i][j] == 'J') {
 81                 ch = map[i][j];
 82                 map[i][j] = '#';
 83                 if (cur == t) {
 84                     //printmap();
 85                     if ( !bfs() ) {
 86                         fmin = (t<fmin) ? t:fmin;
 87                         return 1;
 88                     }
 89                 }
 90                 if (cur < t)
 91                     flg = dfs(t, cur+1);
 92                 map[i][j] = ch;
 93             }
 94             if (flg)
 95                 return 1;
 96         }
 97     }
 98 
 99     return 0;
100 }
101 
102 int pre() {
103     int i, x, y, tmp1, tmp2;
104 
105     tmp1 = 0;
106     for (i=0; i<4; ++i) {
107         x = begx + direct[i][0];
108         y = begy + direct[i][1];
109         if ( check(x, y) && (map[x][y]=='.'||map[x][y]=='J'))
110             tmp1++;
111     }
112 
113     tmp2 = 0;
114     for (i=0; i<4; ++i) {
115         x = endx + direct[i][0];
116         y = endy + direct[i][1];
117         if ( check(x, y) && (map[x][y]=='.'||map[x][y]=='J'))
118             tmp2++;
119     }
120 
121     return tmp1<tmp2 ? tmp1 : tmp2;
122 }
123 
124 int main() {
125     int case_n;
126     int i, j;
127 
128     scanf("%d", &case_n);
129 
130     while (case_n--) {
131         scanf("%d %d %d%*c", &n, &m, &time);
132         for (i=0; i<n; ++i) {
133             scanf("%s", map[i]);
134             for (j=0; j<m; ++j) {
135                 if (map[i][j] == 'S') {
136                     begx = i;
137                     begy = j;
138                 }
139                 if (map[i][j] == 'E') {
140                     endx = i;
141                     endy = j;
142                 }
143             }
144         }
145         if ( !bfs() ) {
146             printf("0
");
147             continue;
148         }
149         fmin = pre();
150         //printf("pre:%d
", fmin);
151         dfs(1,1);
152         //printf("1:%d
", fmin);
153         dfs(2,1);
154         //printf("2:%d
", fmin);
155         dfs(3,1);
156         printf("%d
", fmin);
157     }
158 
159     return 0;
160 }