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?

   A three-dimensional maze problem , It's no different from two dimensions , direct BFS Just fine .

The code is as follows :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> using namespace std; bool map1[][][];
bool vis[][][];
int L,R,C;
int Sl,Sr,Sc,El,Er,Ec; struct state
{
int l,r,c;
int num; state() {}
state(int x,int y,int z,int n):l(x),r(y),c(z),num(n) {}
}; bool judge(int x,int y,int z)
{
if(x<=||x>L||y<=||y>R||z<=||z>C)
return ; if(map1[x][y][z]==)
return ; if(vis[x][y][z])
return ; vis[x][y][z]=;
return ;
} int bfs()
{
queue <state> que;
state temp;
int tl,tr,tc; que.push(state(Sl,Sr,Sc,)); while(!que.empty())
{
temp=que.front();
que.pop(); if(temp.l==El&&temp.r==Er&&temp.c==Ec)
return temp.num; tl=temp.l;
tr=temp.r;
tc=temp.c; if(judge(tl-,tr,tc))
que.push(state(tl-,tr,tc,temp.num+));
if(judge(tl+,tr,tc))
que.push(state(tl+,tr,tc,temp.num+));
if(judge(tl,tr-,tc))
que.push(state(tl,tr-,tc,temp.num+));
if(judge(tl,tr+,tc))
que.push(state(tl,tr+,tc,temp.num+));
if(judge(tl,tr,tc-))
que.push(state(tl,tr,tc-,temp.num+));
if(judge(tl,tr,tc+))
que.push(state(tl,tr,tc+,temp.num+));
} return -;
} int main()
{
char s[];
int ans; ios::sync_with_stdio(false); while(cin>>L>>R>>C)
{
memset(vis,,sizeof(vis)); if(!L&&!R&&!C)
break; for(int i=;i<=L;++i)
for(int j=;j<=R;++j)
{
cin>>s;
for(int k=;k<=C;++k)
switch(s[k-])
{
case 'S':
Sl=i;
Sr=j;
Sc=k;
map1[i][j][k]=;
break;
case 'E':
El=i;
Er=j;
Ec=k;
map1[i][j][k]=;
break;
case '.':
map1[i][j][k]=;
break;
case '#':
map1[i][j][k]=;
break;
}
} ans=bfs(); if(ans!=-)
cout<<"Escaped in "<<ans<<" minute(s).\n";
else
cout<<"Trapped!\n";
} return ;
}

( Simple ) POJ 2251 Dungeon Master,BFS. More articles about

  1. poj 2251 Dungeon Master( bfs )

    subject :http://poj.org/problem?id=2251 Simple 3D bfs Don't explain , 1A,     Code up #include <iostream> #include<cst ...

  2. POJ 2251 Dungeon Master bfs difficulty :0

    http://poj.org/problem?id=2251 bfs, Change two dimensions into three , however 30*30*30=9e3 The space-time complexity of is still enough to withstand #include <cstdio> #inc ...

  3. poj 2251 Dungeon Master (BFS The three dimensional )

    You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of un ...

  4. POJ 2251 Dungeon Master (BFS shortest path )

    In three dimensions BFS shortest path #include <iostream> #include <cstdio> #include <cstring> #include < ...

  5. POJ 2251 Dungeon Master --- The three dimensional BFS( use BFS Find the shortest path )

    POJ 2251 The main idea of the topic :  Give a three-dimensional dungeon , It is required to find out the character 'S' To character 'E' Shortest path , The direction of movement can be up , Next , Left , Right , front , after , Six directions , Every move takes a minute , Ask for the fastest output time . Different L layer ...

  6. POJ.2251 Dungeon Master ( The three dimensional BFS)

    POJ.2251 Dungeon Master ( The three dimensional BFS) Problem analysis You're trapped in a 3D In the dungeon and continue to find the shortest way to escape . Dungeons are made up of cube units , The cube may be full of rocks . It takes one point to move one unit up, down, back, left, right ...

  7. BFS POJ 2251 Dungeon Master

    Subject portal /* BFS: This question is very interesting , It's like an underground city , The picture is three-dimensional , You can go from the previous picture to the corresponding position of the next picture , So that's 3D search , More z Axis */ #include <cstdio> #includ ...

  8. POJ 2251 Dungeon Master( Dungeon Master )

    p.MsoNormal { margin-bottom: 10.0000pt; font-family: Tahoma; font-size: 11.0000pt } h1 { margin-top: ...

  9. POJ 2251 Dungeon Master /UVA 532 Dungeon Master / ZOJ 1940 Dungeon Master( Breadth first search )

    POJ 2251 Dungeon Master /UVA 532 Dungeon Master / ZOJ 1940 Dungeon Master( Breadth first search ) Description You ar ...

Random recommendation

  1. In raspberry pie Raspbian Next installation support Hard Float Of .NET Environmental Science

    [ Digression ] I recently joined a raspberry pie , Officially recommended for system installation Hard Float Of Raspbian, As derived from Debian, therefore Mono What's the best outfit . But the official sources Mono stay Hard Float Of Raspbi ...

  2. Windows Form call R Draw and display

    R The software is very powerful , Can be very good for all kinds of statistics , And can output graphics . Here is an introduction to R Language and C# The way to communicate , And will R The result of the plot is displayed to WinForm UI On the interface . 1 The premise to prepare install R Software , Need to install 32 Bit R Software ,6 ...

  3. 【IOS】 Custom clickable multi text running Lantern YFRollingLabel

    demand A running lantern is needed in the project to show only one message , If the length is right, it doesn't roll , If it's too long, it will cycle . Although I didn't write it , But looking at the code , It's in one. UIView Put two in it UILabel, At the end of the previous one , The other shows . But a little ...

  4. To adapt to laytpl Render template data

    Preface When we read data asynchronously , And also by manual assignment , On the page , So you're too OUT 了 , I'll tell you a new way . That's it  laytpl plug-in unit Use a : Rendering a single piece of data <table id="B ...

  5. MeshDog

    One .TransforMesh 1. CGAL (http://www.cgal.org/download/windows.html#GeneralPrerequisites) Pre installed software 1.1 cma ...

  6. Python- attribute (property)

    stay 2.6 In the version , Added a new way to access class member functions --property. Prototype class property([fget[, fset[, fdel[, doc]]]]) fget: get attribute fset ...

  7. Android Studio Download, install and configure graphic tutorial

    original text http://jingyan.baidu.com/article/9c69d48f56835e13c9024e95.html AndroidStudio Download address :https://develope ...

  8. mysql Business 、 trigger 、 View 、 stored procedure 、 function

    stored procedure : procedure The concept is similar to the function , It's just encapsulating a piece of code , When it comes to executing this code , This can be achieved by calling the stored procedure . In the body of the encapsulated statement , It can be used if/else, case,while Equal control ...

  9. Fast power solution -java Method (int Within limits )

    Thought is , Convert a decimal number into a binary number . The others are very simple . Such as :2 Of 11 The next power ,11 Binary bit of 1011, therefore 2(11) = 2(2(0) + 2(1) + 2(3)); Specific implementation steps , Looking at the code is relatively simple impo ...

  10. e858. Bind keyboard keys to events

    This example creates a number of keystrokes and adds them to the input map of a component. When a ke ...