Escaped in x minute(s).
Trapped!
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
Escaped in 11 minute(s). Trapped!
//一次AC，感觉太爽了！！
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
char map[40][40][40];
int x1,y1,z1,x2,y2,z2;
int dx[]={0,1,0,-1,0,0};
int dy[]={1,0,-1,0,0,0};
int dz[]={0,0,0,0,1,-1};
int n,row,column;
struct Dungeon//地牢
{
int x,y,z;
int time;
friend bool operator < (Dungeon a,Dungeon b)
{
return a.time>b.time;
}
};
bool judge(int xt,int yt,int zt)
{
if(xt>row||xt<1||yt>column||yt<1||zt>n||zt<1) //越界
return 0;
if(map[zt][xt][yt]=='#')
return 0;
return 1;
}
int BFS()
{
priority_queue<Dungeon>q;
Dungeon pos,next;
pos.x=x1;
pos.y=y1;
pos.z=z1;
pos.time=0;
map[z1][x1][y1]='#';
q.push(pos);
while(!q.empty())
{
pos=q.top();
q.pop();
for(int i=0;i<6;++i)
{
next.x=pos.x+dx[i];
next.y=pos.y+dy[i];
next.z=pos.z+dz[i];
next.time=pos.time+1;
if(judge(next.x,next.y,next.z))
{
if(next.x==x2&&next.y==y2&&next.z==z2)
{
return next.time;
}
map[next.z][next.x][next.y]='#';
q.push(next);
}
}
}
return -1;
}
int main()
{
while(~scanf("%d%d%d",&n,&row,&column),n+row+column)
{
getchar();
for(int i=1;i<=n;++i)
{
for(int j=1;j<=row;++j)
{
for(int k=1;k<=column;++k)
{
scanf("%c",map[i][j]+k);
if(map[i][j][k]=='S')
{
z1=i,x1=j,y1=k;
}
else if(map[i][j][k]=='E')
{
z2=i,x2=j,y2=k;
}
}
getchar();
}
getchar();
}
int res;
res=BFS();
if(res==-1) printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n",res);
}
return 0;
}版权声明：本文为博主原创文章，未经博主允许不得转载。
Dungeon Master ZOJ 1940【优先队列+广搜】
原文：http://blog.csdn.net/yuzhiwei1995/article/details/47322077