题意
zjm被困在一个三维的空间中,现在要寻找最短路径逃生!
空间由立方体单位构成。
zjm每次向上下前后左右移动一个单位需要一分钟,且zjm不能对角线移动。
空间的四周封闭。zjm的目标是走到空间的出口。
是否存在逃出生天的可能性?如果存在,则需要多少时间?
Input
输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L,R和C(皆不超过30)。
L表示空间的高度,R和C分别表示每层空间的行与列的大小。
随后L层,每层R行,每行C个字符。
每个字符表示空间的一个单元。’#‘表示不可通过单元,’.‘表示空白单元。
zjm的起始位置在’S’,出口为’E’。每层空间后都有一个空行。
L,R和C均为0时输入结束。
Output
每个空间对应一行输出。
如果可以逃生,则输出如下
Escaped in x minute(s).
x为最短脱离时间。
如果无法逃生,则输出如下
Trapped!
Example
Input
3 4 5
S….
.###.
.##…
###.#
##.##
##…
#.###
####E
1 3 3
S##
#E#
0 0 0
Output
Escaped in 11 minute(s).
Trapped!
思想
本题利用三维+bfs可解:分别走6个方向,最早满足条件的就是最短时间
- 与二维迷宫的不同之处在于:移动方向有六个,坐标(x,y,z)
int move[6][3] = {{0, 0, 1},{0, 0, -1},{0, -1, 0},{0, 1, 0},{1, 0, 0},{-1, 0, 0}};
migong[newnode.z][newnode.x][newnode.y]!='#'&&
newnode.z>=0&&newnode.z<l&&newnode.x>=0&&newnode.x<r&&newnode.y>=0&&newnode.y<c&&
!mark[newnode.z][newnode.x][newnode.y])
- 注意(z,x,y)与(i,j,k)的对应,在三维数组中第一维是本题中的层数(z)
- 注意提前记录起点位置,起点不一定是(0,0,0)
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
char migong[50][50][50];
int move[6][3] = {{0, 0, 1},{0, 0, -1},{0, -1, 0},{0, 1, 0},{1, 0, 0},{-1, 0, 0}};
int l,r,c;
bool mark[50][50][50];
struct node
{
int x,y,z;
int step;
};
node node1;
void bfs()
{
mark[0][0][0]=1;
queue<node> q;
q.push(node1);
while(!q.empty())
{
node1=q.front();
q.pop();
if(migong[node1.z][node1.x][node1.y]=='E')
{
printf("Escaped in %d minute(s).\n",node1.step);
return;
}
for(int i=0;i<6;i++)
{
node newnode;
newnode.z=node1.z+ move[i][0];
newnode.x=node1.x+ move[i][1];
newnode.y=node1.y+ move[i][2];
newnode.step=node1.step;
if(migong[newnode.z][newnode.x][newnode.y]!='#'&&
newnode.z>=0&&newnode.z<l&&newnode.x>=0&&newnode.x<r&&newnode.y>=0&&newnode.y<c&&
!mark[newnode.z][newnode.x][newnode.y])
{
mark[newnode.z][newnode.x][newnode.y]=1;
newnode.step++;
q.push(newnode);
}
}
}
printf("Trapped!\n");
}
int main()
{
while(~scanf("%d%d%d",&l,&r,&c))
{
if(l==0&&r==0&&c==0) return 0;
memset(mark,0,sizeof(mark));
for(int i=0;i<l;i++)
{
for(int j=0;j<r;j++)
{
scanf("%s",migong[i][j]);
for(int k=0;k<c;k++)
{
if(migong[i][j][k]=='S')
{
node1.z=i;
node1.x=j;
node1.y=k;
node1.step=0;
}
}
}
}
mark[0][0][0]=1;
bfs();
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)