搜索专题2 | 3D地宫寻路 POJ - 2251
搜索专题2 | 3D地宫寻路 POJ - 2251
上一篇我们做了一道棋子摆放的题目，采用的是DFS算法，本篇是一篇BFS算法，在刚开始学习搜索算法的时候，会觉得DFS和BFS算法非常相似，因为都是搜索然后得到结果。
二者除了搜索行为不一样，大部分时候都能够处理相同的问题。但是在选用DFS还是BFS时，需要注意的是BFS能够很好的处理最短路径问题，但是BFS需要一个辅助队列来进行逻辑处理。DFS往往用于搜索所有解的情况。
这也是为什么上一题采用DFS，因为需要输出所有的解。
而本题采用BFS，是需要搜索最短路径。
DFS也可以采用迭代加深的方式进行搜索，这样能够在某些情况下减少搜索次数。不过处理最短路径最有效的还是BFS算法，因为最短路径仅需要求出离root节点最近的满足要求的节点。
本题可以让你理解BFS的这种特质，如果采用DFS更容易超时。
题意：
3维的地图，求从S到E的最短路径长度
原题：
Description
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. Is an escape possible? If yes, how long will it take?
Input
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). L is the number of levels making up the dungeon. R and C are the number of rows and columns making up the plan of each level. Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape. If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0Sample Output
Escaped in 11 minute(s).
Trapped!解题步骤：
1 初始化参数
2 bfs，读取队列元素，从6个方向寻找，执行入队列操作
3 执行过程中记录节点是否访问过
地宫寻路参考：
源代码：C++
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 35
using namespace std;
// 位置x,y,z，以及搜索深度d
struct node {
int x, y, z, d;
} s, e;
int L, R, C;
int m[N][N][N], vis[N][N][N];
int ans;
int dx[7] = {0, 0, 0, 0, 1, -1};
int dy[7] = {0, 0, 1, -1, 0, 0};
int dz[7] = {1, -1, 0, 0, 0, 0};
bool ck(int x, int u) {
return x >= 0 && x < u;
}
void bfs() {
// 初始化操作
ans = 0;
memset(vis, 0, sizeof vis);
queue<node> q;
vis[s.x][s.y][s.z] = 1;
s.d = 0;
q.push(s);
// 开始操作队列
while (!q.empty()) {
// 取元素
node u = q.front();
q.pop();
// 如果是终点
if (u.x == e.x && u.y == e.y && u.z == e.z) {
ans = u.d;
return;
}
// 朝6个方向搜索（放入队列）
for (int i = 0; i < 6; i++) {
int nx = u.x + dx[i], ny = u.y + dy[i], nz = u.z + dz[i];
if (ck(nx, L) && ck(ny, R) && ck(nz, C) && !vis[nx][ny][nz] && m[nx][ny][nz]) {
q.push((node){nx, ny, nz, u.d + 1});
// 记录位置是否已经访问
vis[nx][ny][nz] = 1;
}
}
}
}
int main() {
while (scanf("%d%d%d", &L, &R, &C), L) {
memset(m, 0, sizeof m);
for (int i = 0; i < L; i++) {
for (int j = 0; j < R; j++)
for (int k = 0; k < C; k++) {
char c;
scanf(" %c", &c);
// 记录起点和终点
if (c == 'S')
s = (node){i, j, k};
if (c == 'E')
e = (node){i, j, k};
// 设置障碍
if (c != '#')
m[i][j][k] = 1;
}
}
// 开始搜索
bfs();
// 输出答案
if (ans)
printf("Escaped in %d minute(s).\n", ans);
else
puts("Trapped!");
}
return 0;
}
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。