Dungeon Master （BFS与DFS的应用）

个人心得：一开始用DFS弄了半天一直输出不了结果，后面发现并没有进行判断；好不容易能够得出答案，结果超时了，才发现原来要用BFS；

对于DFS：

从一个点开始模拟能走的所有步骤，注意边界条件，走到不能走时返回上一步继续循环；耗时比较大，主要要注意当前的动作

格式的话

void dfs（int step）

{

判断边界

尝试每一种可能

{

注意标记；

继续下一步；

}

BFS广度搜索，能够走得位置都走，将能到达的位置进入队列，当一个位置的所有动作完成时出队列，注意标志不改变，当队列为空时搜索完毕，当然找最小步伐时第一次到达时便是最小步骤！

struct Node

{

int x;//横坐标

int y;//纵坐标

int f;//纪录当下的编号，有时输出路径

int sum;//总步数

}；

将开始的位置放入队列，sum=0，每一种可能判断，若能走标志并且进入队列，此时sum+1；一个位置的所有动作完成后，队列head出列；若查找到，退出，此时的总步数为queue【tail-1】.sum；

放题

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

Sample Output

Escaped in 11 minute(s).
Trapped!

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 using namespace std;
 6 struct Node
 7 {
 8     int x,y,z;
 9     int sum;
10 
11 };
12 int  L,R,C;
13 char mapa[35][35][35];
14 int book[35][35][35];
15 void bfs(int a,int b,int c)
16 {
17     int next[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
18     queue<Node> s;
19     Node n;
20     n.x=a,n.y=b,n.z=c,n.sum=0;
21     book[a][b][c]=1;
22     s.push(n);
23     while(!s.empty())
24     {
25 
26         for(int i=0;i<6;i++)
27         {
28             Node m=s.front();
29             Node kk;
30             int t1=kk.x=m.x+next[i][0];
31             int t2=kk.y=m.y+next[i][1];
32             int t3=kk.z=m.z+next[i][2];
33             kk.sum=m.sum+1;
34             if(t1<1||t2<1||t3<1||t1>L||t2>R||t3>C)
35                 continue;
36             if(mapa[t1][t2][t3]=='E')
37             {
38                 cout<<"Escaped in "<<kk.sum<<" minute(s)."<<endl;
39                 return ;
40 
41 
42             }
43             if(mapa[t1][t2][t3]=='.'&&book[t1][t2][t3]==0)
44             {
45 
46                 s.push(kk);
47                 book[t1][t2][t3]=1;
48 
49 
50 
51 
52             }
53 
54 
55         }
56         s.pop();
57 
58     }
59     cout<<"Trapped!"<<endl;
60 }
61 int main()
62 {
63 
64     while(cin>>L>>R>>C)
65     {
66         int a,b,c;
67         if(!L&&!R&&!C)
68             break;
69             for(int i=1;i<=L;i++)
70               for(int j=1;j<=R;j++)
71                 for(int k=1;k<=C;k++)
72         {
73             cin>>mapa[i][j][k];
74             if(mapa[i][j][k]=='S') {a=i,b=j,c=k;}
75 
76         }
77         memset(book,0,sizeof(book));
78         bfs(a,b,c);
79       
80     }
81 
82   return 0;
83 
84 }

Dungeon Master （BFS与DFS的应用）

相关推荐