题目大意
在一个城堡里有一只火龙,它要飞出这个城堡,有6个方向,上,下,左,右,前,后,可以飞行。每飞一次记录一分钟,’#’代表城墙,不能飞,空地可以飞,但记录时间。现在让你输入一个城堡R, L, C,R代表层数, L代表行,R代表列, S代表起点,E代表终点。找出它最快几步能飞出城堡。(他可以从一层跳到另一层的空地)
思路
典型的广搜题,用一个3维数组来存这个棋盘,先记录起点和终点的位置。先将它的起点的位置存入队列,在一个循环内对这个位置进行6次方向不同的操作,(这个是BFS的关键所在)如果它没有越界或者是碰到墙壁,就说明它可以走,将该位置存入队列。直到该位置和终点的位置想同时,结束输出所用的时间。
代码
# include <stdio.h>
# include <string.h>
# include <queue>
# define max 30
using namespace std;
char G[max][max][max];
int dir[6][3] = {{1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1}};//代表6个方向
int h, l, r;
typedef struct node1
{
int x,y,z,step;
}node;
int ans;
int DFS(node s, node e)
{
queue<node> Q;
Q.push(s);
while(Q.size())
{
node s = Q.front();
Q.pop();
if( s.z == e.z && s.x == e.x && s.y == e.y)
return s.step;
for(int i = 0; i<6; i++)
{
node q = s;//关键所在,让每一步互不影响
q.z += dir[i][2];
q.x += dir[i][0];
q.y += dir[i][1];
if( G[q.z][q.x][q.y] != '#' && q.x>=0 && q.x<l && q.y>=0 && q.y<r && q.z>=0 && q.z<h)
{
q.step+=1;
G[q.z][q.x][q.y] = '#';//关键所在 不让它往回走
Q.push(q);
}
}
}
return -1;
}
int main(void)
{
int i,j,k;
node s,e;
while(scanf("%d%d%d", &h,&l, &r), h+l+r)
{
for(i = 0; i<h; i++)
for(j = 0; j<l; j++)
{
scanf("%s",G[i][j]);
for(k = 0; k<r; k++)
{
if(G[i][j][k] == 'S')
{
s.z = i;//层数
s.x = j;
s.y = k;
s.step = 0;
}
if(G[i][j][k] == 'E')
{
e.z = i;
e.x = j;
e.y = k;
}
}
}
ans = DFS(s,e);
if(ans != -1)
{
printf("Escaped in %d minute(s).\n", ans);
}
else
{
printf("Trapped!\n");
}
}
return 0;
}