专栏首页饶文津的专栏【POJ 2251】Dungeon Master(bfs)

【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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HDU 5839】Special Tetrahedron(计算几何)

    共面判断就是用叉乘计算出ijk三点所在面的法向量,然后判断il向量是否和法向量垂直,是则共面。

    饶文津
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津
  • 「2017 Multi-University Training Contest 1」2017多校训练1

    饶文津
  • SPOJ 375 边操作

    给一颗树,每条边有一个权值。有两种操作:1、修改某条边的值;2、询问a、b两点路径上边权的最大值。

    用户2965768
  • 经典笔试题-JAVA实现快速排序算法

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • Contest 176 - LeetCode 1353. Maximum Number of Events That Can Be Attended (贪心)

    题意:有n个节目,每个节目有一个持续的天数,你一天只能看一个节目,问你这么多天最多能看几个节目

    ShenduCC
  • C++的黑魔法: 用四种方式实现add!

    C++作为一门多范式编程语言, 今天我们来看看实现一个简单的加法, 我们可以有多么不同的四种方式!

    陈小龙Cheney
  • 1001 舒适的路线 2006年

    1001 舒适的路线 2006年 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Descrip...

    attack
  • HDU 5677 ztr loves substring(回文串加多重背包)

    ztr loves substring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

    ShenduCC
  • 搜索(4)

    mathor

扫码关注云+社区

领取腾讯云代金券