POJ 2251 Dungeon Master
Dungeon MasterTime Limit: 1000MS Memory Limit: 65536K
Total Submissions: 12655 Accepted: 4912
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 易做图 up the dungeon.
R and C are the number of rows and columns 易做图 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!
Source
Ulm Local 1997
考察点: bfs搜索
[cpp] view plaincopy
#include <stdio.h>
#include <string.h>
#include <math.h>
int a[50][50][50],status[50][50][50],sum[50][50][50];
int stax,stay,staz,endy,endx,endz,t,n,m;
int vex[]={0,0,0,0,1,-1};
int vey[]={0,0,-1,1,0,0};
int vez[]={-1,1,0,0,0,0};
char s1[100];
struct num
{
int x,y,z;
}queue[1000000];
int main()
{
int bfs();
int i,j,s,k,x;
char c;
while(scanf("%d %d %d%*c",&t,&n,&m)!=EOF)
{
if(!n&&!m&&!t)
{
break;
}
for(i=0;i<=t-1;i++)
{
for(j=0;j<=n-1;j++)
{
for(x=0;x<=m-1;x++)
{
scanf("%c",&c);
if(c=='#')
{
a[i][j][x]=0;
}else if(c=='.')
{
a[i][j][x]=1;
}else if(c=='S')
{
a[i][j][x]=1;
staz=i; stax=j; stay=x;
}else if(c=='E')
{
a[i][j][x]=1;
endz=i; endx=j; endy=x;
}
}
getchar();
}
gets(s1);
}
k=bfs();
if(k!=-1)
{
printf("Escaped in %d minute(s).\n",k);
}else
{
printf("Trapped!\n");
}
}
return 0;
}
int bfs()
{
int i,j,base,top,x,y,z,k,xend,yend,zend;
base=top=0;
queue[top].x=stax; queue[top].y=stay; queue[top++].z=staz;
memset(status,0,sizeof(status));
status[stax][stay][staz]=1;
memset(sum,0,sizeof(sum));
k=0;
while(base<top)
{
x=queue[base].x; y=queue[base].y; z=queue[base++].z;
if(x==endx&&y==endy&&z==endz)
{
k=1;
break;
}
for(i=0;i<=5;i++)
{ www.zzzyk.comwww.zzzyk.com
xend=x+vex[i]; yend=y+vey[i]; zend=z+vez[i];
if(xend>=0&&xend<=n-1&¥d>=0&¥d<=m-1&&zend>=0&&zend<=t-1&&!status[xend][
补充:软件开发 , C++ ,
- 更多C/C++疑问解答:
- 关于c++的cout输出的问题。
- 在学校里学过C和C++,不过学的很一般,现在自学C#,会不会很难?
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
- c++数据结构内部排序问题,整数排序
- 2012九月计算机二级C语言全国题库,,急求急求
- 如果assert只有一个字符串作为参数,是什么意思呢?
- C语言中,哪些运算符具有左结合性,哪些具有右结合性,帮忙总结下,谢谢了!
- 为什么用结构体编写的程序输入是,0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型,用C或C++都行,多谢各位大侠啊,非常感谢!
- 为什么这个程序求不出公式?
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊