POJ 2251
题目大意： 给出一三维空间的地牢,要求求出由字符'S'到字符'E'的最短路径，移动方向可以是上，下，左，右，前，后，六个方向，每移动一次就耗费一分钟，要求输出最快的走出时间。不同L层的地图，相同RC坐标处是相连通的。(.可走，#为墙)
解题思路:从起点开始分别往6个方向进行BFS(即入队),并记录步数,直至队为空.若一直找不到,则困住。
/* POJ 2251 Dungeon Master --- 三维BFS(用BFS求最短路) */
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; int n, m, o; //n行m列,o为层
char mapp[][][];
bool visit[][][]; //标记访问状态 /* 构造队列元素 (点位置+步数)*/
struct Point{
int x, y, z;
int step;
Point(){}
Point(int a, int b, int c, int d) :x(a), y(b), z(c), step(d){}
}; /* 判断点是否满足访问条件 */
inline bool judge(Point tmp){
if (mapp[tmp.x][tmp.y][tmp.z] == '#' || visit[tmp.x][tmp.y][tmp.z]
|| tmp.x < || tmp.x >= o || tmp.y < || tmp.y >= n
|| tmp.z < || tmp.z >= m
){
return ;
}
return ;
} /* x0为深度 y0,z0为同一层坐标 */
void bfs(int x0, int y0,int z0){
queue<Point> q;
bool found = ;
visit[x0][y0][z0] = ; //起点标记已访问
q.push(Point(x0, y0, z0, ));
while (!q.empty()){
Point tmp = q.front(); q.pop();
if (mapp[tmp.x][tmp.y][tmp.z] == 'E'){
//找到终点，搜索结束，输出最短路
printf("Escaped in %d minute(s).\n", tmp.step);
found = ;
break;
}
else{
Point tmp2;
++tmp.step; //步数必定增加 //往上一层
tmp2 = tmp;
tmp2.x = tmp.x - ;
if (judge(tmp2)){
visit[tmp2.x][tmp2.y][tmp2.z] = ;
q.push(tmp2);
} //往下一层
tmp2 = tmp;
tmp2.x = tmp.x + ;
if (judge(tmp2)){
visit[tmp2.x][tmp2.y][tmp2.z] = ;
q.push(tmp2);
} //以下四种为同一层 //往上一行
tmp2 = tmp;
tmp2.y = tmp.y - ;
if (judge(tmp2)){
visit[tmp2.x][tmp2.y][tmp2.z] = ;
q.push(tmp2);
} //往下一行
tmp2 = tmp;
tmp2.y = tmp.y + ;
if (judge(tmp2)){
visit[tmp2.x][tmp2.y][tmp2.z] = ;
q.push(tmp2);
} //往左一列
tmp2 = tmp;
tmp2.z = tmp.z - ;
if (judge(tmp2)){
visit[tmp2.x][tmp2.y][tmp2.z] = ;
q.push(tmp2);
} //往右一列
tmp2 = tmp;
tmp2.z = tmp.z + ;
if (judge(tmp2)){
visit[tmp2.x][tmp2.y][tmp2.z] = ;
q.push(tmp2);
} }//else
}//while
if (!found){
printf("Trapped!\n");
}
} int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif int sx, sy, sz;
while (scanf("%d%d%d", &o, &n, &m) == && (m + n + o)){
memset(visit, , sizeof visit);
for (int i = ; i < o; ++i){
for (int j = ; j < n; ++j){
scanf("%s", mapp[i][j]);
for (int k = ; k < m; ++k){
if (mapp[i][j][k] == 'S'){
sx = i;
sy = j;
sz = k;
}
}//for(k)
}//for(j) n行
}//for(i) o层
bfs(sx, sy, sz); //sx是深度
} return ;
}
