题目链接：http://poj.org/problem?id=2251
题意：
有一个高度为L,长度为R,宽度为C的三维迷宫,用'#'代表迷宫内的障碍物,‘.’代表迷宫内的可行区域,‘S’代表起点位置,'E'代表终点位置,每次可以往东、西、南、北、上、下六个方向移动,每移动一次花费1min,问从起点到达终点的最短时间t,然后输出“Escaped in t minute(s).”,如果不能到达,输出“Trapped!”.
思路：
算是三维的迷宫问题吧,类比普通迷宫求最短路径问题,直接用BFS解决就好了,注意BFS时走过的路标记下,迷宫中除了'.'可以走外,'E'也可以走.
代码：
1 #include <iostream>
2 #include <cmath>
3 #include <cstdio>
4 #include <cstring>
5 #include <cstdlib>
6 #include <stack>
7 #include <queue>
8 #include <vector>
9 #include <algorithm>
10 #include <string>
11
12 typedef long long LL;
13 using namespace std;
14 const int MAXN = 30;
15 char maze[MAXN + 3][MAXN + 3][MAXN + 3];
16 int L, R, C;
17 const int stepX[] = { 0, 0, 1, -1, 0, 0};//六个可选方向
18 const int stepY[] = {-1, 1, 0, 0, 0, 0};
19 const int stepZ[] = { 0, 0, 0, 0, 1, -1};
20
21 typedef struct Dungeon{int x; int y; int z; int step;}Dun;
22 Dun st, ed;//起点和终点
23
24 int BFS(Dun st) {//从起点开始BFS
25 int ans = -1;
26 queue<Dun> Qu;
27 Qu.push(st);
28 maze[st.x][st.y][st.z] = '*';//访问过得位置 置为‘*'，不再访问
29 while(!Qu.empty()) {
30 Dun now = Qu.front();
31 Qu.pop();
32 ans = now.step;
33 if(now.x == ed.x && now.y == ed.y && now.z == ed.z) break;//到达终点
34 for(int i = 0; i < 6; i++) {
35 Dun nex;
36 nex.x = now.x + stepX[i], nex.y = now.y + stepY[i], nex.z = now.z + stepZ[i], nex.step = now.step + 1;//走到当前位置的步数等于上一个位置的步数加1
37 if(maze[nex.x][nex.y][nex.z] == '.' || maze[nex.x][nex.y][nex.z] == 'E'){
38 Qu.push(nex);
39 maze[nex.x][nex.y][nex.z] = '*';
40 }
41 }
42 }
43 return ans;
44 }
45
46 int main() {
47 while(scanf("%d%d%d", &L, &R, &C) == 3 && (L != 0 || R != 0 || C != 0)) {
48 memset(maze, '!', sizeof(maze));
49 st.x = st.y = st.z = ed.x = ed.y = ed.z = ed.step = -1;
50 st.step = 0;
51 for(int i = 1; i <= L; i++) {
52 for(int j = 1; j <= R; j++) {
53 getchar();
54 for(int k = 1; k <= C; k++) {
55 maze[i][j][k] = getchar();
56 if(maze[i][j][k] == 'S') st.x = i, st.y = j, st.z = k;
57 else if(maze[i][j][k] == 'E') ed.x = i, ed.y = j, ed.z = k;
58 }
59 }
60 getchar();
61 }
62 int ans = BFS(st);
63 if(ans > 0) printf("Escaped in %d minute(s).
", ans);
64 else printf("Trapped!
");
65 }
66 return 0;
67 }