HDU1010 Tempter of the Bone

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const int maxn = 10;
 7 int vis[maxn][maxn], dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
 8 char mapp[maxn][maxn];
 9 int n, m, t, flag, cnt, si, sj, di, dj;
10 
11 void DFS(int x, int y, int cnt)
12 {
13     if(x == di && y == dj) //如果走到终点
14     {
15         if(cnt == t) flag = 1; //并且步数恰好等于时间，门正好打开。
16         return ; //不过是否走出去，都必须返回
17     }
18     if(cnt >= t) return ; //超过时间再继续走已经没有意义了。
19     if(mapp[x][y] == ‘X‘) return ; //X的地方是不能走的。
20     vis[x][y] = 1; //标记为已经走过
21     for(int i = 0; i < 4; i++) //四个方向搜索
22     {
23         int xx = x + dir[i][0]; 
24         int yy = y + dir[i][1];
25         
26         //初始化时边界之外的地方都标记为X，所以此处包括边界的判断。
27         if(mapp[xx][yy] == ‘X‘ || vis[xx][yy]) continue; 
28         vis[xx][yy] = 1; //标记为已走过
29         DFS(xx, yy, cnt + 1); //搜索
30         vis[xx][yy] = 0; //回溯
31         if(flag) return ; //这步至关重要，否则会TLE
32     }
33     return ;
34 }
35 
36 int main()
37 {
38     while(~scanf("%d %d %d", &n, &m, &t) && (n || m || t))
39     {
40         memset(vis, 0, sizeof(vis)); //全部标记为没有走过
41         memset(mapp, ‘X‘, sizeof(mapp)); //边界之外也标记为X
42         for(int i = 1; i <= n; i++)
43         {
44             for(int j = 1; j <= m; j++)
45             {
46                 scanf(" %c", &mapp[i][j]);
47                 if(mapp[i][j] == ‘S‘) si = i, sj = j;
48                 if(mapp[i][j] == ‘D‘) di = i, dj = j;
49             }
50         }
51         
52         //非常经典的剪枝，否者会TLE
53         //如果走到该点所用的最少步数都超过t，是不可能走到的。
54         //后面一个条件是奇偶判断的问题，需要好好思考
55         if(abs(si-di) + abs(sj-dj) > t || (si+sj+di+dj+t) % 2 == 1 )
56         {
57             printf("NO\n");
58             continue;
59         }
60 
61         flag = 0, cnt = 0;
62         DFS(si, sj, 0);
63         if(flag) printf("YES\n"); //如果flag==1,则表明走出来了。
64         else printf("NO\n");
65     }
66     return 0;
67 }