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)


相关推荐

  • sha1给出了三种新的sha版本_开发版和稳定版哪个好

    sha1给出了三种新的sha版本_开发版和稳定版哪个好在进行百度地图等地图开发时,需要申请一个SHA1,方法流程如下:1.找到文件debug.keystore所在位置,一般在C盘的.android目录下。2.使用jdk自带的keytool工具。3.进入win+r输入cmd进入cmd窗口,进入debug.keystore所在目录,使用keytool工具,示例:C:\Users\SYY\.android>D:\SYYData\.download\IDEA-C\jdks\bin\keytool-list-v-keystoredebug.keys

  • 通过工具SecureCRTPortable将项目部署到服务器上

    通过工具SecureCRTPortable将项目部署到服务器上1.将项目打包2.打开工具连接指定的ip下面是一些命令  tab键可以有一些提示功能  ls查看服务器当前目录  lls查看硬盘当前目录  其实就是linux系统命令,服务器是正常命令,操作本电脑的就在前面加个l  例如lslls,cdlcd…

  • js获取当前年月日时分秒_js获取当前系统时间年月日

    js获取当前年月日时分秒_js获取当前系统时间年月日vardate=newDate();date.getYear();//获取当前年份(2位)date.getFullYear();//获取完整的年份(4位)date.getMonth();//获取当前月份(0-11,0代表1月)date.getDate();//获取当前日(1-31)date.getDay();//获取当前星期X(0-6,0代表星期天)date.getT…

  • IE7\IE6 图片上传预览

    IE7\IE6 图片上传预览

  • onedrive申请1T免费空间_drive百度云

    onedrive申请1T免费空间_drive百度云微软推出学生活动。教育网邮箱账户可以免费领取onedrive1T容量,免费获取OFFICE365帐号。首先我们要到https://xkx.me/领取一个可以获得福利的临时邮箱。(最好输入一个ID/前缀)提示:通常你能在5分钟内收到邮件。然后打开https://www.microsoft.com/en-us/education/products/office?tab=students这时注意了,一定要等这个网站完全加载完再输入邮箱!!!!!也就是不能让网站处于下图的一种.

  • 宏基因组数据分析:差异分析(LEfSe安装使用及LDA score计算)

    宏基因组数据分析:差异分析(LEfSe安装使用及LDA score计算)文章目录简介安装简介安装报错:Collectingpackagemetadata(current_repodata.json):doneSolvingenvironment:failedwithinitialfrozensolve.Retryingwithflexiblesolve.Solvingenvironment:failedwithrepodatafromcurrent_repodata.json,willretrywithnextre

发表回复

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

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