专题（六）双指针、BFS与图论——AcWing 1113. 红与黑 AcWing 1096. 地牢大师
本文共 1789 字，大约阅读时间需要 5 分钟。
【题目描述】这是一个三维迷宫的最短路径寻找问题，采用广度优先搜索（BFS）算法来解决。迷宫由多个层组成，每层是一个二维网格，需要从起点出发，找到通往出口的最短路径。
【思路】将传统的BFS算法从二维扩展到三维。在这个问题中，迷宫的三个维度分别表示行、列和高度（层）。需要注意的是，传统的BFS需要考虑多个移动方向，包括上下左右和进入下一层。在实现时，需要使用三维数组来表示迷宫的状态，并记录访问情况以避免重复计算。
【代码解析】主要代码如下：
import java.io.;import java.util.public class Node {int x, y, z, step;Node(int xx, int yy, int zz, int tt) {x = xx;y = yy;z = zz;step = tt;}public class Main {static int N = 110;static char[][][] g = new char[N][N][N];static int[] dx = {0, 0, 1, 0, -1, 0};static int[] dy = {0, 0, 0, -1, 0, 1};static int[] dz = {1, -1, 0, 0, 0, 0};public static String bfs(int sx, int sy, int sz, int R, int C, int T) {Queue
q = new LinkedList<>();q.offer(new Node(sx, sy, sz, 0));g[sx][sy][sz] = '#';while (!q.isEmpty()) {Node h = q.poll();int x = h.x, y = h.y, z = h.z, step = h.step;for (int i = 0; i < 6; i++) {int a = x + dx[i];int b = y + dy[i];int c = z + dz[i];if (a < 0 || a >= R || b < 0 || b >= C || c < 0 || c >= T) continue;if (g[a][b][c] == '#') continue;if (g[a][b][c] == 'E') return "Escaped in " + (step + 1) + " minute(s).";q.offer(new Node(a, b, c, step + 1));g[a][b][c] = '#';}}return "Trapped!";}public static void main(String[] args) throws Exception {BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));while (true) {String[] s = bf.readLine().split(" ");if (s.length == 0) break;try {T = Integer.parseInt(s[0]);R = Integer.parseInt(s[1]);C = Integer.parseInt(s[2]);if (T == 0 && R == 0 && C == 0) break;int sx = 0, sy = 0, sz = T;for (int i = 0; i < T; i++) {bf.readLine();for (int j = 0; j < R; j++) {String str = bf.readLine();for (int k = 0; k < C; k++) {g[j][k][i] = str.charAt(k);if (g[j][k][i] == 'S') {sx = j;sy = k;sz = i;}}}bf.readLine();}System.out.println(bfs(sx, sy, sz, R, C, T));} catch (NumberFormatException e) {break;}}}} 转载地址：http://okpzz.baihongyu.com/