前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【POJ 2251】Dungeon Master(bfs)

【POJ 2251】Dungeon Master(bfs)

作者头像
饶文津
发布2020-06-02 12:18:35
2980
发布2020-06-02 12:18:35
举报
文章被收录于专栏:饶文津的专栏

题意

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

题解

bfs

代码

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-02-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 题解
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档