POJ - 2251 Dungeon Master （三维迷宫问题 bfs）
看到三维bfs，当然少不了二维的bfs，先来看看二维bfs的迷宫问题怎么解决，就是多了一个维度其他没有啥的
kuangbin 简单搜索 - 迷宫问题 POJ - 3984 （二维迷宫问题 bfs）
详情看代码！！！逻辑有点绕，实际上跟二维是差不多的，如果不理解的话可以看看二维的。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
//#define int ll
#define INF 0x3f3f3f3f
using namespace std;
int read()
{
int w = 1, s = 0;
char ch = getchar();
while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
//最大公约数
}int gcd(int x,int y) {
if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后
//递归终止条件千万不要漏了，辗转相除法
return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y)//计算x和y的最小公倍数
{
return x * y / gcd(x, y);//使用公式
}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int maxn = 33;
char Map[maxn][maxn][maxn];//迷宫地图
bool vis[maxn][maxn][maxn];
int n,m,h;
//按照坐标遍历6个方向查看可行路线。
int Next[6][3]={{0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0}};
struct Node {
int x, y, z;
int steps;
};
struct Node Start, End;
int l, r, c;
//三维bfs
int bfs() {
int next[6][3] = { { -1,0,0 },{ 0,-1,0 },{ 0,0,-1 },{ 1,0,0 },{ 0,1,0 },{ 0,0,1 } };
queue<Node> q;
q.push(Start);
vis[Start.x][Start.y][Start.z] = true;
//如果队列不空入队
while (!q.empty()) {
struct Node temp = q.front();
q.pop();
if (Map[temp.x][temp.y][temp.z] == 'E')
return temp.steps;
//枚举6个方向
for (int i = 0; i < 6; i++) {
struct Node add;
//以这个方向行走后所得到的新的坐标
add.x = temp.x + next[i][0];
add.y = temp.y + next[i][1];
add.z = temp.z + next[i][2];
add.steps = temp.steps + 1;
//判断该坐标是否合法
//将这个位置标记为无法行走（即岩石）
if (add.x >= 0 && add.y >= 0 && add.z >= 0 && add.x < r && add.y < c && add.z < l && Map[add.x][add.y][add.z] != '#' && !vis[add.x][add.y][add.z])
{
vis[add.x][add.y][add.z] = true;
q.push(add);
}
}
}
return -1;
}
int main() {
while (scanf("%d %d %d", &l, &r, &c) != EOF)
{
memset(vis, false, sizeof(vis));//初始化vis
if (l == 0 && r == 0 && c == 0)
break;
for (int i = 0; i<l; i++) {
for (int j = 0; j<r; j++) {
for (int k = 0; k<c; k++) {
cin >> Map[j][k][i];
if (Map[j][k][i] == 'S') {
Start.x = j; Start.y = k; Start.z = i;
}
}
}
}
int res = bfs();//进行三维BFS
if (res != -1)//否则按照题目中给出的格式输出res
printf("Escaped in %d minute(s).\n", res);
else
printf("Trapped!\n");//如果无法到达输出"Trapped!"
}
return 0;
}