题意:给出一三维空间的地牢,要求求出由字符'S'到字符'E'的最短路径移动方向可以是上,下,左,右,前,后,六个方向,每移动一次就耗费一分钟,要求输出最快的走出时间。不同L层的地图,相同RC坐标处是连通的,“#”不可通过,“.”可走。
分析:最短路Bfs,和二维的基本一样,就是原来4个方向,现在6个方向,原来数组是二维,现在是三维,也相当于模板题了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std; char map[][][];
int vis[][][];
int k,n,m,sx,sy,sz,ex,ey,ez;
int dx[]={-,,,,,};
int dy[]={,,-,,,};
int dz[]={,,,,,-};
struct node
{
int x,y,z,step;
}; int check(int x,int y,int z)
{
if(x<||y<||z<||x>=k||y>=n||z>=m||map[x][y][z]=='#'||vis[x][y][z])
return ;
return ;
} int bfs()
{
node a,next;
queue<node> Q;
a.x=sx;
a.y=sy;
a.z=sz;
a.step=;
vis[sx][sy][sz]=;
Q.push(a);
while(!Q.empty())
{
a=Q.front();
Q.pop();
if(a.x==ex&&a.y==ey&&a.z==ez)
return a.step;
for(int i=;i<;++i)
{
next=a;
next.x=a.x+dx[i];
next.y=a.y+dy[i];
next.z = a.z+dz[i];
if(check(next.x,next.y,next.z))
continue;
vis[next.x][next.y][next.z]=;
next.step=a.step+;
Q.push(next);
}
}
return ;
} int main()
{
while(scanf("%d%d%d",&k,&n,&m),n+m+k)
{
for(int i=;i<k;++i)
{
for(int j=;j<n;++j)
{
scanf("%s",map[i][j]);
for(int r=;r<m;++r)
{
if(map[i][j][r]=='S')
{
sx=i;
sy=j;
sz=r;
}
else if(map[i][j][r]=='E')
{
ex=i;
ey=j;
ez=r;
}
}
}
}
memset(vis,,sizeof(vis));
int ans;
ans=bfs();
if(ans)
printf("Escaped in %d minute(s).\n",ans);
else
printf("Trapped!\n");
}
return ;
}