题目大意:
一个三维的图(30*30*30),求出从起点S到终点E的最短距离(有可能走不到) '.'可以走,'#'不能走 。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 50
using namespace std;
char map[N][N][N]={0};
bool vis[N][N][N]={0};
int dis[N][N][N]={0};
int move[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int x,y,z;
struct point
{
int x;int y;int z;
};
point e,s;
void input()
{
char l;
l=getchar();
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
for(int h=1;h<=z;h++)
{
scanf("%c",&map[i][j][h]);
if(map[i][j][h]=='S')
{
s.x=i;
s.y=j;
s.z=h;
}
if(map[i][j][h]=='E')
{
e.x=i;
e.y=j;
e.z=h;
}
}
l=getchar();
}
l=getchar();
}
}
bool is_inmap(point t)
{
if(t.x<=0||t.x>x)return 0;
if(t.y<=0||t.y>y)return 0;
if(t.z<=0||t.z>z)return 0;
return 1;
}
void bfs()
{
queue<point>poi;
poi.push(s);
vis[s.x][s.y][s.z]=1;
while(!poi.empty())
{
for(int i=0;i<6;i++)
{
point t;
t.x=poi.front().x+move[i][0];
t.y=poi.front().y+move[i][1];
t.z=poi.front().z+move[i][2];
if(vis[t.x][t.y][t.z]==1)continue;
if(!is_inmap(t))continue;
if(map[t.x][t.y][t.z]=='#')continue;
dis[t.x][t.y][t.z]=dis[poi.front().x][poi.front().y][poi.front().z]+1;
vis[t.x][t.y][t.z]=1;
poi.push(t);
}
poi.pop();
}
}
int main()
{
while(cin>>x>>y>>z)
{
if(x==0&&y==0&&z==0)break;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
input();
bfs();
if(dis[e.x][e.y][e.z]==0)cout<<"Trapped!"<<endl;
else cout<<"Escaped in "<<dis[e.x][e.y][e.z]<<" minute(s)."<<endl;
}
}