POJ 2251 Dungeon Master
题意：有一个地图，三维，走的方向是上下，左右，前后。问你最小步数从起始点走到出口。
思路：三维的BFS，就是多加一组状态，需要细心（不细心如我就找了半个多小时的错误才AC）
/**
Sample Input
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
Sample Output
Escaped in 11 minute(s).
Trapped!
**/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 35;
int L,R,C;
char maps[maxn][maxn][maxn];
int d[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];
int dx[]={1,0,-1,0,0,0};
int dy[]={0,1,0,-1,0,0};
int dz[]={0,0,0,0,-1,1}; //状态分别是右，前，左，后，下，上
int ans;
struct node{
int x;
int y;
int z;
node(int _x=0,int _y=0,int _z=0):x(_x),y(_y),z(_z){}//虽然很好用，但是不能开node数组赋值？？？
};
//这个边界范围一定要弄清楚，x,y,z不要想当然，看清再写范围。
bool can(int x,int y,int z){
if(x<0||x>=L){
return 0;
}
else if(y<0||y>=R){
return 0;
}
else if(z<0||z>=C){
return 0;
}
else return 1;
}
int bfs(int x,int y,int z){
queue<node>q;
memset(d,-1,sizeof(d));
memset(vis,0,sizeof(vis));
node u = node(x,y,z);
q.push(u);
d[u.x][u.y][u.z] = 0;
while(!q.empty()){
u = q.front();
q.pop();
if(maps[u.x][u.y][u.z]=='S'){
return d[u.x][u.y][u.z];
}
for(int i=0;i<6;i++){
node a;
a.x = u.x+dx[i];
a.y = u.y+dy[i];
a.z = u.z+dz[i];
if(!vis[a.x][a.y][a.z]&&maps[a.x][a.y][a.z]!='#'&&can(a.x,a.y,a.z)){
d[a.x][a.y][a.z] = d[u.x][u.y][u.z]+1;
vis[a.x][a.y][a.z] = 1;
q.push(a);
}
}
}
return -1;
}
int main()
{
while(~scanf("%d%d%d",&L,&R,&C)){
if(!L&&!R&&!C) break;
for(int i=0;i<L;i++){
for(int j=0;j<R;j++){
scanf("%s",maps[i][j]);
}
getchar();
}
for(int i=0;i<L;i++)
for(int j=0;j<R;j++)
for(int k=0;k<C;k++){
if(maps[i][j][k]=='E'){ //逆着走可以减少无法出去情况判断的复杂度
ans = bfs(i,j,k);
}
}
if(ans!=-1)
printf("Escaped in %d minute(s).\n",ans);
else printf("Trapped!\n");
}
return 0;
}
