BUPT2017 wintertraining(16) #5 B

POJ - 2251

题意

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;

}