1253 Dungeon Master-阿里云开发者社区

1253 Dungeon Master

2017-07-30 1730

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 题目链接：http://noi.openjudge.cn/ch0205/1253/http://poj.org/problem?id=2251总时间限制: 1000ms 内存限制: 65536kB描述You are trapped in a 3D dungeon and need to...

题目链接：

http://noi.openjudge.cn/ch0205/1253/

http://poj.org/problem?id=2251

总时间限制: 1000ms 内存限制: 65536kB

描述

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?

输入

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.

输出

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!

样例输入

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

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

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

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

0 0 0

样例输出

Escaped in 11 minute(s).
Trapped!

题目大意与算法分析：
这题是一个三维的迷宫题目，其中用‘.’表示空地，用‘#’表示障碍物，'S'表示出发点，
'E'表示终点，求从起点到终点的最小移动次数。
解法和二维类似，只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动，
每次都只能移动到相邻的空位，每次需要花费一分钟，求从起点到终点最少需要多久。

输入有若干组测试数据，每一组数据格式如下：
首先输入z,x,y表示三维迷宫的规模，有z层，每层是x行y列。 (z,x,y都在30以内.)
然后输入z层的数据，每一层是x*y的字符数组，行内字符之间无空格。
当输入的z，x，y都为0时表示输入结束。

对每一组测试数据，输出最少需要的时间，格式如"Escaped in 11 minute(s)."，每组数据的结果占一行。
假如无法到达，输出"Trapped!".

这题用BFS解，每次去队首元素，如果是终点则输出结果移动的次数，否则，从该点开始分别
向东南西北上下移动（如果可以走的话）并继续搜，如果到队列为空还没搜到解法，则说明无解。

题解可以参考：
http://www.cnblogs.com/ACShiryu/archive/2011/07/23/2114994.html
http://blog.csdn.net/libin56842/article/details/23702395

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<queue>
  4 using namespace std;
  5 
  6 struct obj
  7 {
  8     int zz,xx,yy;
  9     int step;//到达该点的步数 
 10 };
 11 
 12 int z,x,y;
 13 char a[33][33][33];
 14 queue<struct obj> q;
 15 struct obj start,End;
 16 bool flag;
 17 
 18 int dz[6]={0,0,0,0,1,-1};//上右下左前后 
 19 int dx[6]={-1,0,1,0,0,0};
 20 int dy[6]={0,1,0,-1,0,0};
 21 void BFS();//广搜，数据全部在全局变量 
 22 
 23 int main(int argc, char *argv[])
 24 {
 25     int i,j,k;
 26 
 27     while(scanf("%d%d%d",&z,&x,&y)!=EOF)
 28     {
 29         getchar();//吸收回车 
 30         if(z==0&&x==0&&y==0) break;
 31         
 32         //输入三维迷宫 
 33         for(k=0;k<z;k++)
 34         {
 35             for(i=0;i<x;i++)
 36             {
 37                 for(j=0;j<y;j++)
 38                 {
 39                     a[k][i][j]= getchar();
 40                     if(a[k][i][j]=='E') 
 41                     {
 42                         a[k][i][j]='.';
 43                         End.zz=k;
 44                         End.xx=i;
 45                         End.yy=j;
 46                     }
 47                     else if(a[k][i][j]=='S')
 48                     {
 49                         start.zz=k;
 50                         start.xx=i;
 51                         start.yy=j;
 52                         start.step=0;
 53                     }
 54                 }
 55                 getchar();//吸收回车
 56             }
 57             getchar();//吸收回车
 58         }
 59         
 60         flag=false;//尚未找到目的地 
 61         BFS();
 62         if(flag==true)
 63             printf("Escaped in %d minute(s).\n",End.step);
 64         else printf("Trapped!\n");
 65     }
 66     return 0;
 67 }
 68 
 69 void BFS()//广搜，数据全部在全局变量
 70 {
 71     int i,tzz,txx,tyy;
 72     struct obj temp;
 73     
 74     while(!q.empty()) q.pop();//清空队列
 75      
 76     q.push(start);//出发点入队
 77     while(!q.empty())
 78     {
 79         for(i=0;i<6;i++)
 80         {
 81             tzz=(q.front()).zz+dz[i];
 82             txx=(q.front()).xx+dx[i];
 83             tyy=(q.front()).yy+dy[i];
 84             if(tzz>=0&&tzz<z&&txx>=0&&txx<x&&tyy>=0&&tyy<y&&a[tzz][txx][tyy]=='.')
 85             {
 86                 temp.zz=tzz;
 87                 temp.xx=txx;
 88                 temp.yy=tyy;
 89                 temp.step=(q.front()).step+1;
 90                 a[tzz][txx][tyy]='#';
 91                 q.push(temp);
 92                 if(temp.zz==End.zz&&temp.xx==End.xx&&temp.yy==End.yy)
 93                 {
 94                     End.step=temp.step;
 95                     flag=true;
 96                     return ;
 97                 }
 98             }
 99         }
100         q.pop();
101     }
102     return ;
103 }