【题目描述】
这题是一个三维的迷宫题目，其中用‘.’表示空地，‘#’表示障碍物，‘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){
//到达终点，退出bfsprintf("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;
}
代码提交结果
