地牢大师问题

前言

在之前的博客里面，我们介绍了bfs 基础算法的模版和应用,这里我们再挑战一下自己，尝试一个更高水平的题目，加深一下对bfs算法的理解。如果对bfs更多知识感兴趣的话，可以点个关注，后续会继续更新有关知识点的。
往期的文章如下：
红与黑问题（bfs+dfs 解法）

题目描述

你现在被困在一个三维地牢中，需要找到最快脱离的出路！

地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。

向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。

你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范围。

请问，你有可能逃脱吗？
如果可以，需要多长时间？

输入格式
输入包含多组测试数据。

每组数据第一行包含三个整数 L,R,C
分别表示地牢层数，以及每一层地牢的行数和列数。

接下来是 L 个 R 行 C 列的字符矩阵，用来表示每一层地牢的具体状况。

每个字符用来描述一个地牢单元的具体状况。

其中, 充满岩石障碍的单元格用”#”表示，不含障碍的空单元格用”.”表示，你的起始位置用”S”表示，终点用”E”表示。

每一个字符矩阵后面都会包含一个空行。

当输入一行为”0 0 0”时，表示输入终止。

输出格式
每组数据输出一个结果，每个结果占一行。

如果能够逃脱地牢，则输出”Escaped in x minute(s).”，其中X为逃脱所需最短时间。

如果不能逃脱地牢，则输出”Trapped!”。

数据范围
1≤L,R,C≤100
输入样例：

3 4 5
S....
.###.
.##..
###.######
#####
##.##
##...#####
#####
#.###
####E1 3 3
S##
#E#
###0 0 0

输出样例：

Escaped in 11 minute(s).
Trapped!

题目分析

输入处理

可能有的小伙伴是 按照z , x , y 的顺序输入的，其实大可不必，这里的z , x , y
是对称的，也就是说我们对于 z , x , y 三个方向都没有特定的要求，可以随意选取，那么我们只要照常输入就行，相当于交换了坐标系

移动方式【和二维的对比】

看图：在算法坐标系中，二维一般是这样的

3维看图：

因为每次移动一个长度单位，所以我们在这里是以1为计量单位表示方向。

边界判断问题的解决

接触过bfs算法题目的小伙伴肯定会对边界判断感到不耐烦，这里教大家一个方法摆脱边界判断：
首先将整个地图全部设成#障碍状态，这样后面就不会走到外面去【关键步骤】

memset(g,'#',sizeof g);

其次输入的时候从 1 开始，这里可以避免边界问题，假设我们的输入从 0 开始，那么就会出现 -1 的意外状况

for(int i=1;i<=l;i++){for(int j=1;j<=r;j++){for(int k=1;k<=c;k++){cin>>g[i][j][k];if(g[i][j][k]=='S'){sx=i,sy=j,sz=k;}if(g[i][j][k]=='E'){ex=i,ey=j,ez=k;}}}}

最后，封死所有走过的路
假设我们不封堵，我们能够走回走过的点，就说明一定有个环，这就无解了，其次，
封过走过的路之后吗，得到的一定就是最小值
一般bfs的处理方法会用一个s t [N]的数组记录是否走过，这里相当于将我们的地图数组一箭双雕。

代码

解释都在代码注释当中啦

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 107;char g[N][N][N];//用于存储地图数据
int d[N][N][N];//用于记录步数
int dx[6]={1,0,-1,0,0,0};
int dy[6]={0,1,0,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int l,r,c;
struct node{int x,y,z;//这里需要对bfs引入 3 哥数据，也就是遍历的队列要包含 3 哥元素//所以我们用结构体存储
};
int bfs(int sx,int sy,int sz){g[sx][sy][sz]='#';*//将走过的路封死d[sx][sy][sz]=0;//将开始的起点举例设为 0 queue<node> q;q.push({sx,sy,sz});while(!q.empty()){auto t=q.front();q.pop();for(int i=0;i<6;i++){// cout<<dx[i]<<' '<<dy[i]<<' '<<dz[i]<<endl;int a=t.x+dx[i];int b=t.y+dy[i];int c=t.z+dz[i];// cout<<a<<b<<c<<endl;// cout<<a<<' '<<b<<' '<<c<<endl;if(g[a][b][c]!='#'){//直接判断是否为障碍就行//不需要俺么劳心费神的操作// cout<<g[a][b][c]<<endl;if(g[a][b][c]=='.'){q.push({a,b,c});g[a][b][c]='#';d[a][b][c]=d[t.x][t.y][t.z]+1;// cout<<a<<' '<<b<<' '<<c<<endl;// puts("");}if(g[a][b][c]=='E'){return d[t.x][t.y][t.z]+1;}}}}return -1;
}
int main(){while(cin>>l>>r>>c,l||r||c){memset(g,'#',sizeof g);//由于要输入多个数据memset(d,-1,sizeof d);//每次要将数据清零int sx,sy,sz;int ex,ey,ez;for(int i=1;i<=l;i++){for(int j=1;j<=r;j++){for(int k=1;k<=c;k++){cin>>g[i][j][k];if(g[i][j][k]=='S'){sx=i,sy=j,sz=k;//找到最开始的点}if(g[i][j][k]=='E'){ex=i,ey=j,ez=k;//找到结束的点，后来发现这步操作没有用}}}}int t=bfs(sx,sy,sz);if(t==-1) printf("Trapped!");else printf("Escaped in %d minute(s).",t);puts("");}return 0;
}

总结

以上就是地牢大师的解法，喜欢的小伙伴可以点个赞啦
记住免去边界处理的关键在于将整个地图数组障碍化，起始的输入也是从 1 开始，最大程度上面减小边界处理步骤。