【HDOJ】1253 胜利大逃亡

经典的BFS，需要注意的是当前时间超过最小时间，输出-1。同时，队列为空时还未返回，证明并未找到终点（可能终点为墙）。此时也应该输出-1，这个部分容易wa。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <queue>
 5 using namespace std;
 6 
 7 #define MAXNUM 50
 8 #define SETPOS(pos,xx,yy,zz,tt) pos.x=xx;pos.y=yy;pos.z=zz;pos.t=tt;
 9 
10 typedef struct {
11     int x, y, z;
12     int t;
13 } pos_st;
14 
15 int map[MAXNUM][MAXNUM][MAXNUM];
16 int visit[MAXNUM][MAXNUM][MAXNUM];
17 int direct[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
18 int a, b, c, mintime;
19 queue<pos_st> poss;
20 
21 void bfs(int x, int y, int z, int t) {
22     pos_st pos, tmp;
23 
24     SETPOS(pos,x,y,z,t);
25     poss.push(pos);
26     visit[x][y][z] = 1;
27 
28     while (!poss.empty()) {
29         pos = poss.front();
30         poss.pop();
31 
32         if (pos.t > mintime) {
33             printf("-1
");
34             return;
35         }
36         if (pos.x==a-1 && pos.y==b-1 && pos.z==c-1) {
37             printf("%d
", pos.t);
38             return;
39         }
40         for (int i=0; i<6; ++i) {
41             SETPOS(tmp, pos.x+direct[i][0], pos.y+direct[i][1], pos.z+direct[i][2], pos.t+1);
42             if (tmp.x<0 || tmp.x>=a || tmp.y<0 || tmp.y>=b || tmp.z<0 || tmp.z>=c)
43                 continue;
44             if (visit[tmp.x][tmp.y][tmp.z] || map[tmp.x][tmp.y][tmp.z]==1)
45                 continue;
46             visit[tmp.x][tmp.y][tmp.z] = 1;
47             poss.push(tmp);
48         }
49     }
50 
51     printf("-1
");
52 }
53 
54 int main() {
55     int case_n;
56     int i, j, k;
57 
58     scanf("%d", &case_n);
59 
60     while (case_n--) {
61         scanf("%d%d%d%d", &a,&b,&c,&mintime);
62         for (i=0; i<a; ++i)
63             for (j=0; j<b; ++j)
64                 for (k=0; k<c; ++k)
65                     scanf("%d", &map[i][j][k]);
66         memset(visit, 0, sizeof(visit));
67         while (!poss.empty())
68             poss.pop();
69         bfs(0,0,0,0);
70     }
71 
72     return 0;
73 }