【POJ 2251】Dungeon Master（bfs）---饶文津

题意

3维的地图，求从S到E的最短路径长度

题解

bfs

代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define N 35 using namespace std; struct node{ int x,y,z,d; }s,e; int L,R,C; int m[N][N][N],vis[N][N][N]; int ans; int dx[7]={0,0,0,0,1,-1}; int dy[7]={0,0,1,-1,0,0}; int dz[7]={1,-1,0,0,0,0}; bool ck(int x,int u){ return x>=0&&x<u; } void bfs(){ ans=0; memset(vis,0,sizeof vis); queue<node>q; vis[s.x][s.y][s.z]=1; s.d=0; q.push(s); while(!q.empty()){ node u=q.front(); q.pop(); if(u.x==e.x&&u.y==e.y&&u.z==e.z){ ans=u.d; return; } for(int i=0;i<6;i++){ int nx=u.x+dx[i],ny=u.y+dy[i],nz=u.z+dz[i]; if(ck(nx,L)&&ck(ny,R)&&ck(nz,C)&&!vis[nx][ny][nz]&&m[nx][ny][nz]){ q.push((node){nx,ny,nz,u.d+1}); vis[nx][ny][nz]=1; } } } } int main() { while(scanf("%d%d%d",&L,&R,&C),L){ memset(m,0,sizeof m); for(int i=0;i<L;i++){ for(int j=0;j<R;j++) for(int k=0;k<C;k++){ char c; scanf(" %c",&c); if(c=='S')s=(node){i,j,k}; if(c=='E')e=(node){i,j,k}; if(c!='#')m[i][j][k]=1; } } bfs(); if(ans)printf("Escaped in %d minute(s).n",ans); else puts("Trapped!"); } return 0; } ---来自腾讯云社区的---饶文津