Kimi LeetCode LCP 31. 变换的迷宫 Java实现

以下是 LeetCode LCP 31. 变换的迷宫 的 Java 实现。题目回顾迷宫为 N \times M地形随时间变化。小力从 (0,0) 出发出口始终在 (n-1,m-1)。每时刻可选择上下左右移动一步或停留原地。有两个魔法卷轴各可使用一次- 临时消除术将指定位置在下一个时刻变为空地- 永久消除术将指定位置永久变为空地判断在迷宫变化结束前含最后时刻能否到达出口。解题思路采用分层图 BFS状态扩展思想- 状态定义为 (时刻 i, 坐标 x, y, 卷轴使用情况 s)- s 有 4 种- 0 NONE_USED未使用任何卷轴- 1 ONLY_TEMP已使用临时消除术- 2 ONLY_PERM已使用永久消除术- 3 TEMP_PERM两个都已使用- 对于永久消除术需要记录消除的位置 (px, py)因为之后该位置在所有时刻都变为空地。- 每个时刻可以向 5 个方向扩展上下左右 停留。Java 实现javaimport java.util.*;class Solution {// 四个方向 停留private static final int[] DX {0, 0, 1, -1, 0};private static final int[] DY {1, -1, 0, 0, 0};// 卷轴使用状态private static final int NONE_USED 0; // 未使用private static final int ONLY_TEMP 1; // 只用临时private static final int ONLY_PERM 2; // 只用永久private static final int TEMP_PERM 3; // 两个都用了// 状态值到达该状态的最小步数以及永久消除的位置private static class StateValue {int dist; // 到达该状态的最小步数int px, py; // 永久消除的位置ONLY_PERM/TEMP_PERM时有效StateValue(int dist, int px, int py) {this.dist dist;this.px px;this.py py;}}// BFS 状态private static class State {int layer; // 当前时刻int x, y; // 当前坐标int sc; // 卷轴使用状态StateValue val; // 状态值State(int layer, int x, int y, int sc, StateValue val) {this.layer layer;this.x x;this.y y;this.sc sc;this.val val;}}public boolean escapeMaze(ListListString maze) {int layers maze.size();int r maze.get(0).size();int c maze.get(0).get(0).length();// f[i][x][y][sc] 表示时刻 i在 (x,y)卷轴状态为 sc 的最优状态// 由于 layers 100, r,c 50可以用四维数组StateValue[][][][] f new StateValue[layers][r][c][4];// 初始化for (int i 0; i layers; i) {for (int x 0; x r; x) {for (int y 0; y c; y) {for (int sc 0; sc 4; sc) {f[i][x][y][sc] new StateValue(Integer.MAX_VALUE, -1, -1);}}}}// 起点(0,0)时刻0未使用卷轴步数为0f[0][0][0][NONE_USED] new StateValue(0, -1, -1);QueueState q new LinkedList();q.offer(new State(0, 0, 0, NONE_USED, f[0][0][0][NONE_USED]));while (!q.isEmpty()) {State cur q.poll();int cl cur.layer;int cx cur.x;int cy cur.y;int csc cur.sc;StateValue cval cur.val;int nextLayer cl 1;if (nextLayer layers) continue; // 超出时间范围for (int dir 0; dir 5; dir) {int nx cx DX[dir];int ny cy DY[dir];// 越界检查if (nx 0 || nx r || ny 0 || ny c) continue;char cell maze.get(nextLayer).get(nx).charAt(ny);// 情况1下一时刻该位置是空地可以直接走if (cell .) {if (cval.dist 1 f[nextLayer][nx][ny][csc].dist) {f[nextLayer][nx][ny][csc] new StateValue(cval.dist 1, cval.px, cval.py);q.offer(new State(nextLayer, nx, ny, csc, f[nextLayer][nx][ny][csc]));}continue;}// 情况2下一时刻该位置是陷阱 #// 子情况2.1已经用了永久消除术且消除的就是这个位置if (csc ONLY_PERM || csc TEMP_PERM) {if (cval.px nx cval.py ny) {// 永久消除的位置可以通行if (cval.dist 1 f[nextLayer][nx][ny][csc].dist) {f[nextLayer][nx][ny][csc] new StateValue(cval.dist 1, cval.px, cval.py);q.offer(new State(nextLayer, nx, ny, csc, f[nextLayer][nx][ny][csc]));}continue;}}// 子情况2.2使用卷轴来通过// 2.2a当前只用了临时可以在这里用永久消除术if (csc ONLY_TEMP) {// 使用永久消除术将 (nx, ny) 永久消除if (cval.dist 1 f[nextLayer][nx][ny][TEMP_PERM].dist) {f[nextLayer][nx][ny][TEMP_PERM] new StateValue(cval.dist 1, nx, ny);q.offer(new State(nextLayer, nx, ny, TEMP_PERM, f[nextLayer][nx][ny][TEMP_PERM]));}}// 2.2b当前只用了永久可以在这里用临时消除术if (csc ONLY_PERM) {// 使用临时消除术下一时刻该位置变为空地if (cval.dist 1 f[nextLayer][nx][ny][TEMP_PERM].dist) {f[nextLayer][nx][ny][TEMP_PERM] new StateValue(cval.dist 1, cval.px, cval.py);q.offer(new State(nextLayer, nx, ny, TEMP_PERM, f[nextLayer][nx][ny][TEMP_PERM]));}}// 2.2c当前什么都没用可以选择用临时或永久if (csc NONE_USED) {// 使用临时消除术if (cval.dist 1 f[nextLayer][nx][ny][ONLY_TEMP].dist) {f[nextLayer][nx][ny][ONLY_TEMP] new StateValue(cval.dist 1, -1, -1);q.offer(new State(nextLayer, nx, ny, ONLY_TEMP, f[nextLayer][nx][ny][ONLY_TEMP]));}// 使用永久消除术if (cval.dist 1 f[nextLayer][nx][ny][ONLY_PERM].dist) {f[nextLayer][nx][ny][ONLY_PERM] new StateValue(cval.dist 1, nx, ny);q.offer(new State(nextLayer, nx, ny, ONLY_PERM, f[nextLayer][nx][ny][ONLY_PERM]));}}}}// 检查是否能在任意时刻到达终点for (int i 0; i layers; i) {for (int sc 0; sc 4; sc) {if (f[i][r - 1][c - 1][sc].dist ! Integer.MAX_VALUE) {return true;}}}return false;}}关键点总结要点 说明状态设计 (时刻, x, y, 卷轴状态) 四维状态类似分层图永久消除术 需要记录消除位置 (px, py)后续时刻该位置始终可通行临时消除术 只对下一个时刻有效使用后状态变为 ONLY_TEMPBFS 扩展 每时刻向 5 个方向4方向停留扩展时间复杂度 O(layers \times r \times c \times 4 \times 5)在数据范围内可接受示例验证输入 输出 解释[[.#.,#..],[...,.#.],[.##,.#.],[..#,.#.]] true 可以在时刻3到达终点[[.#.,...],[...,...]] false 时间不够无法到达示例37层大迷宫 false 道路不通无法到达