POJ 2251-Dungeon Master(BFS)[通俗易懂]

POJ 2251-Dungeon Master(BFS)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Dungeon Master
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 17007   Accepted: 6620

Description

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. 

Is an escape possible?

If yes, how long will it take? 

Input

The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). 

L is the number of levels making up the dungeon. 

R and C are the number of rows and columns making up the plan of each level. 

Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a ‘#’ and empty cells are represented by a ‘.’. Your starting position is indicated by ‘S’ and the exit by the letter ‘E’. There’s a single blank line after each level. Input is terminated by three zeroes for L, R and C.

Output

Each maze generates one line of output. If it is possible to reach the exit, print a line of the form 

Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape. 

If it is not possible to escape, print the line 

Trapped!

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
3维地图给起点和终点搜最短路。

。刷dfs专题刷出来这玩意也是醉了。。

BFS暴搜
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 360
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,m,sx,sy,sz,A,B,C;
bool vis[105][105][105];
char ma[105][105][105];
struct node
{
    int x,y,z,step;
};
int mv[6][3]={{0,0,1},{0,0,-1},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0}};
void bfs()
{
    queue <node> Q;
    node  t;
    t.x=sx;t.y=sy;t.z=sz;t.step=0;
    vis[sx][sy][sz]=1;
    Q.push(t);
    while(!Q.empty())
    {
        node f=Q.front();Q.pop();
        if(ma[f.x][f.y][f.z]=='E')
        {
			printf("Escaped in %d minute(s).\n",f.step);
			return ;
        }
        for(int i=0;i<6;i++)
        {
            t.x=f.x+mv[i][0];
            t.y=f.y+mv[i][1];
            t.z=f.z+mv[i][2];
            if(0<=t.x&&t.x<A&&0<=t.y&&t.y<B&&0<=t.z&&t.z<C&&!vis[t.x][t.y][t.z]&&ma[t.x][t.y][t.z]!='#')
            {
                vis[t.x][t.y][t.z]=1;
                t.step=f.step+1;
                Q.push(t);
            }
        }
    }
    puts("Trapped!");
}
int main()
{
    while(scanf("%d%d%d",&A,&B,&C)!=EOF)
    {
    	if(!A&&!B&&!C)break;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<A;i++)
            for(int j=0;j<B;j++)
				scanf("%s",ma[i][j]);
		for(int i=0;i<A;i++)
			for(int j=0;j<B;j++)
				for(int k=0;k<C;k++)
				if(ma[i][j][k]=='S')
			    {
					sx=i;sy=j;sz=k;
					break;
		        }
            bfs();
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116741.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java项目毕业设计:基于springboot+vue的电影视频网站系统「建议收藏」

    Java项目毕业设计:基于springboot+vue的电影视频网站系统「建议收藏」运行环境:开发工具:IDEA/Eclipse数据库:MYSQL5.7应用服务:Tomcat7/Tomcat8使用框架springboot+vue项目介绍影城管理系统的主要使用者分为管理员和用户,实现功能包括管理员:首页、个人中心、用户管理、电影类型管理、放映厅管理、电影信息管理、购票统计管理、系统管理、订单管理,用户前台:首页、电影信息、电影资讯、个人中心、后台管理、在线客服等功能。由于本网站的功能模块设计比较全面,所以使得整个影城管理系统信息管理的过程得以实现。效果图控制器类

  • 物联网架构图_物联网的架构

    物联网架构图_物联网的架构

  • 大数据实时项目(采集部分)[通俗易懂]

    大数据实时项目(采集部分)[通俗易懂]第一章 实时需求概览1实时需求与离线需求的比较离线需求,一般是根据前一日的数据生成报表,虽然统计指标、报表繁多,但是对时效性不敏感。实时需求,主要侧重于对当日数据的实时监控,通常业务

  • Linux安装PS_linux 安装命令

    Linux安装PS_linux 安装命令导读pstack命令可显示每个进程的栈跟踪。pstack命令必须由相应进程的属主或root运行。可以使用pstack来确定进程挂起的位置。此命令允许使用的唯一选项是要检查的进程的PID。实例pstree以树结构显示进程pstree-pwork|grepadsshd(22669)—bash(22670)—ad_preprocess(4551)-+-{ad_preproc…

  • 卡片式电脑介绍

    卡片式电脑介绍

    2021年11月13日
  • 网站部署ssl证书_阿里云ssl证书部署教程

    网站部署ssl证书_阿里云ssl证书部署教程阿里云续费SSL证书下载证书文件在正式服务器上部署IIS部署阿里云部署步骤:步骤一:下载文件1、登录SSL证书控制台。2、在左侧导航栏,单击SSL证书。3、定位到已签发的SSL证书,单击操作列下的下载。4、在证书下载面板,单击IIS服务器类型后的下载5、解压缩已下载的SSL证书(IIS)压缩包。此时,证书已保存在本地计算机中,导入到服务器端即可步骤二:导入到服务器中1、在服务器按Win+R键,打开运行。2、输入mmc,单击确定3、为本地计算机添加证书管理单元。3.1、在

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号