1248：Dungeon Master(一本通)
该文章由 AnonymousUser在 2020年10月07日 23:22:00发布
【题目描述】
这题是一个三维的迷宫题目，其中用‘.’表示空地，‘#’表示障碍物，‘S’表示起点，‘E’表示终点，求从起点到终点的最小移动次数，解法和二维的类似，只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动，每次都只能移到相邻的空位，每次需要花费一分钟，求从起点到终点最少要多久。
【输入】
多组测试数据。
一组测试测试数据表示一个三维迷宫：
前三个数，分别表示层数、一个面的长和宽，后面是每层的平面图。前三个数据为三个零表示结束。
【输出】
最小移动次数。
【输入样例】
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
【输出样例】
Escaped in 11 minute(s). Trapped!
最终代码内容：
#include<iostream>
#include<queue>
#include <string>//为了使用memset函数
#include <stdio.h>
using namespace std;
const int N=101;
int vis[N][N][N];
char map[N][N][N];
int X,Y,Z;
struct node{
int x,y,z;
int step;
};
int dir[6][3]={
{1,0,0},
{-1,0,0},
{0,1,0},
{0,-1,0},
{0,0,1},
{0,0,-1}
};
queue<node> q;
void bfs(node endPoint){//bfs的终止条件
memset(vis,0, sizeof(vis));//初始化访问数组
node first = q.front();
int step=0;
while(!q.empty())
{
node first = q.front();
q.pop();
step=first.step;
if(first.x==endPoint.x&&first.y==endPoint.y&&first.z==endPoint.z){//到达终点，退出bfs
printf("Escaped in %d minute(s).\n",step);
while (!q.empty()){
q.pop();
}
return;
}
for (int i = 0; i < 6; ++i) {
int nx = first.x+dir[i][0];
int ny=first.y+dir[i][1];
int nz=first.z +dir[i][2];
if(nx>=0&&nx<X&&ny>=0&&ny<Y&&nz>=0&&nz<Z&&map[nx][ny][nz]=='.'&&vis[nx][ny][nz]==0){
vis[nx][ny][nz]=1;
q.push({nx,ny,nz,step+1});
}
}
}
printf("Trapped!\n");
}
int main()
{
int x,y,z,endx,endy,endz;
while(scanf("%d%d%d",&X,&Y,&Z)!=EOF&&X&&Y&&Z){
for (int i = 0; i <X ; ++i) {
for (int j = 0; j < Y; ++j) {
scanf("%s",map[i][j]);
}
}
for(int i=0;i<X;i++)
for(int j=0;j<Y;j++)
for(int k=0;k<Z;k++)
{
if(map[i][j][k]=='S')
{
// printf("init s\n");
x=i;
y=j;
z=k;
}
if(map[i][j][k]=='E')
{
// printf("init end \n");
endx=i;
endy=j;
endz=k;
map[i][j][k]='.';
}
}
q.push({x,y,z,0});//放入队头元素
bfs({endx,endy,endz,0});
}
return 0;
}
代码提交结果
共0条评论
暂无评论