BFS模板
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
char g[N][N][N];
bool st[N][N][N];
int dis[N][N][N];
int n,m,h;
struct node{
int x,y,z;
};
bool check(int x,int y,int z)
{
if(x>=0 && x<n && y>=0 && y<m && z>=0 && z<h && dis[z][x][y]==-1 && g[z][x][y]!='#')
{
return true;
}
return false;
}
int bfs(node start)
{
queue<node>q;
q.push(start);
memset(dis,-1,sizeof dis);
//初始化否则答案会比正确答案小1
dis[start.z][start.x][start.y]=0;
int dx[]={1,0,-1,0,0,0},dy[]={0,1,0,-1,0,0},dz[]={0,0,0,0,1,-1};
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<6;i++)
{
int x=t.x+dx[i];
int y=t.y+dy[i];
int z=t.z+dz[i];
if(check(x,y,z))
{
dis[z][x][y]=dis[t.z][t.x][t.y]+1;
if(g[z][x][y]=='E')
{
return dis[z][x][y];
}
q.push({x,y,z});
}
}
}
return -1;
}
int main()
{
while(cin>>h>>n>>m,h||n||m)
{
node start;
for(int i=0;i<h;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<m;k++)
{
cin>>g[i][j][k];
if(g[i][j][k]=='S')
{
start={j,k,i};
}
}
}
}
int res=bfs(start);
if(res==-1)
{
puts("Trapped!");
}
else
{
cout<<"Escaped in "<<res<<" minute(s)."<<endl;
}
}
return 0;
}