题目链接：http://poj.org/problem?id=2251 我能说我一上来就被题目描述吓到了，然后又被题意吓到了么？ 其实它的本质是一道不折不扣的水题，常规的三维空间广搜，写着写着就出来了，中间因为被坐标问题绕蒙圈了写了很多错误，但是最后拐回来了，空间想象力是个伤啊。。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 struct data
10 {
11 int x, y, z;
12 }S, T;
13 const int dir[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
14 queue<data> Q;
15 char s[35][35];
16 int l, r, c, map[35][35][35], G[35][35][35];
17 bool inMap(int x, int y, int z)
18 {
19 return x >= 0 && x < l && y >= 0 && y < r && z >= 0 && z < c;
20 }
21 void init()
22 {
23 for (int i = 0; i < l; i++)
24 for (int j = 0; j < r; j++)
25 for (int k = 0; k < c; k++)
26 {
27 if (G[i][j][k] == 2) {S.x = i; S.y = j; S.z = k;}
28 if (G[i][j][k] == 3) {T.x = i; T.y = j; T.z = k;}
29 }
30 memset(map, -1, sizeof(map));
31 }
32 void bfs()
33 {
34 Q.push(S);
35 map[S.x][S.y][S.z] = 0;
36 data u, v;
37 while (!Q.empty())
38 {
39 u = Q.front();
40 Q.pop();
41 int x = u.x, y = u.y, z = u.z;
42 for (int i = 0; i < 6; i++)
43 {
44 int xx = x + dir[i][0];
45 int yy = y + dir[i][1];
46 int zz = z + dir[i][2];
47 if (!inMap(xx, yy, zz) || G[xx][yy][zz] == 1) continue;
48 if (map[xx][yy][zz] == -1 || map[x][y][z] + 1 < map[xx][yy][zz])
49 {
50 map[xx][yy][zz] = map[x][y][z] + 1;
51 v.x = xx; v.y = yy; v.z = zz;
52 Q.push(v);
53 }
54 }
55 }
56 }
57 int main()
58 {
59 while (~scanf("%d%d%d", &l, &r, &c))
60 {
61 if (!(l + r + c)) break;
62 for (int i = 0; i < l; i++)
63 {
64 for (int j = 0; j < r; j++) scanf("%s", s[j]);
65 for (int j = 0; j < r; j++)
66 for (int k = 0; k < c; k++)
67 {
68 if (s[j][k] == '#') G[i][j][k] = 1;
69 if (s[j][k] == '.') G[i][j][k] = 0;
70 if (s[j][k] == 'S') G[i][j][k] = 2;
71 if (s[j][k] == 'E') G[i][j][k] = 3;
72 }
73 }
74 init();
75 bfs();
76 if (map[T.x][T.y][T.z] == -1) printf("Trapped!\n");
77 else printf("Escaped in %d minute(s).\n", map[T.x][T.y][T.z]);
78 }
79 return 0;
80 }
81
|