LeetCode 499. 迷宫 III
题目描述
题意分析
小球选定方向后会一直滚动，直到墙前才能再次选择方向；途中经过洞则立即落入。求滚动总格数最少的入洞路线，同距离时返回字典序最小的方向字符串，无法入洞则返回
"impossible"。字符串长度是滚动次数，不是经过的格数。
解法：Dijkstra + 路径字典序
核心思路
[!blue]
把起点以及滚动后能停下的位置看成图节点。从一个位置选方向滚动到另一个位置，构成一条边，边权是实际经过的格数；洞可能在途中，因此模拟滚动时一到洞就停止。这些边的长度不同，普通 BFS 按操作次数分层不能保证滚动距离最短，应使用 Dijkstra。
每个位置保存一对最优信息：
dist[x][y]是最短距离，bestPath[x][y]是达到该距离时字典序最小的方向序列。最小堆也按这两个条件排序，先比较距离，相同再比较路径。起点的距离为零、路径为空，其他位置距离为INF。从堆中取出一个有效状态后，分别模拟四个方向。若一格也不能移动，就不存在有效操作，不追加方向字符；否则把滚动格数加到距离上，把本次方向追加到路径末尾。新距离更小，或者距离相同而路径更小时，都需要更新目标位置并入堆。
只保留同一位置的最小路径不会丢失更优后续：较短的到达距离接上相同后续仍然较短；等距离的两条不同路径不可能互为严格前缀，因为同一方向序列确定同一滚动过程，额外走一段回到相同位置必然增加正距离。因此等距离时，字典序先后的差别发生在已有字符内，追加相同后缀不会改变优劣。
有效边权都为正，到达某位置的更短前驱会先被堆处理，所以取出的当前最优状态可以用于后续扩展。堆里可能还保留该位置此前的旧记录，弹出时要同时核对距离和路径，任一已经过期就跳过。搜索结束后，洞位置保存的就是距离优先、字典序次之的最佳答案。
解题步骤
- 初始化距离表、路径表与按双关键字排序的最小堆，将起点入堆。
- 取出状态，跳过不再等于当前最优记录的旧项。
- 沿四个方向滚动到墙前或洞内，计算经过格数，跳过原地不动的方向。
- 对得到的停点按距离和字典序进行松弛，改进时更新记录并入堆。
- 全部候选处理完后，返回洞的路径；没有找到入洞路径则返回
"impossible"。
代码实现
class Solution {
private static final int INF = 1_000_000_000;
private static final int[] DX = {
1,
0,
0,
-1,
};
private static final int[] DY = {
0,
-1,
1,
0,
};
private static final String[] DIR = {
"d",
"l",
"r",
"u",
};
private static class State {
int x;
int y;
int dist;
String path;
State(int x, int y, int dist, String path) {
this.x = x;
this.y = y;
this.dist = dist;
this.path = path;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m = maze.length;
int n = maze[0].length;
int[][] dist = new int[m][n];
String[][] bestPath = new String[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dist[i], INF);
for (int j = 0; j < n; j++) {
bestPath[i][j] = "";
}
}
PriorityQueue<State> pq =
new PriorityQueue<>(
(a, b) -> {
if (a.dist != b.dist) {
return a.dist - b.dist;
}
return a.path.compareTo(b.path);
});
dist[ball[0]][ball[1]] = 0;
pq.offer(new State(ball[0], ball[1], 0, ""));
while (!pq.isEmpty()) {
State cur = pq.poll();
if (cur.dist != dist[cur.x][cur.y] || !cur.path.equals(bestPath[cur.x][cur.y])) {
continue;
}
for (int d = 0; d < 4; d++) {
int x = cur.x;
int y = cur.y;
int steps = 0;
while (true) {
int nx = x + DX[d];
int ny = y + DY[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 1) {
break;
}
x = nx;
y = ny;
steps++;
// 途中进入洞就停止滚动，不必继续到墙边。
if (x == hole[0] && y == hole[1]) {
break;
}
}
// 不能移动的方向不构成有效操作，不能追加到路径中。
if (steps == 0) {
continue;
}
int ndist = cur.dist + steps;
String npath = cur.path + DIR[d];
// 距离相同但方向序列更小，也必须更新并重新入堆。
if (ndist < dist[x][y]
|| (ndist == dist[x][y]
&& (bestPath[x][y].isEmpty()
|| npath.compareTo(bestPath[x][y]) < 0))) {
dist[x][y] = ndist;
bestPath[x][y] = npath;
pq.offer(new State(x, y, ndist, npath));
}
}
}
String answer = bestPath[hole[0]][hole[1]];
return answer.isEmpty() ? "impossible" : answer;
}
}
import "container/heap"
type State struct {
x int
y int
dist int
path string
}
type MinHeap []State
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
if h[i].dist != h[j].dist {
return h[i].dist < h[j].dist
}
return h[i].path < h[j].path
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(State)) }
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func findShortestWay(maze [][]int, ball []int, hole []int) string {
m := len(maze)
n := len(maze[0])
const inf = int(1e9)
dist := make([][]int, m)
best := make([][]string, m)
for i := 0; i < m; i++ {
dist[i] = make([]int, n)
best[i] = make([]string, n)
for j := 0; j < n; j++ {
dist[i][j] = inf
best[i][j] = ""
}
}
dx := []int{
1,
0,
0,
-1,
}
dy := []int{
0,
-1,
1,
0,
}
dir := []string{
"d",
"l",
"r",
"u",
}
dist[ball[0]][ball[1]] = 0
best[ball[0]][ball[1]] = ""
h := &MinHeap{}
heap.Init(h)
heap.Push(h, State{x: ball[0], y: ball[1], dist: 0, path: ""})
for h.Len() > 0 {
cur := heap.Pop(h).(State)
if cur.dist != dist[cur.x][cur.y] || cur.path != best[cur.x][cur.y] {
continue
}
for d := 0; d < 4; d++ {
x, y := cur.x, cur.y
steps := 0
for {
nx, ny := x+dx[d], y+dy[d]
if nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 1 {
break
}
x, y = nx, ny
steps++
// 途中进入洞就停止滚动，不必继续到墙边。
if x == hole[0] && y == hole[1] {
break
}
}
// 不能移动的方向不构成有效操作，不能追加到路径中。
if steps == 0 {
continue
}
ndist := cur.dist + steps
npath := cur.path + dir[d]
// 距离相同但方向序列更小，也必须更新并重新入堆。
if ndist < dist[x][y] || (ndist == dist[x][y] && (best[x][y] == "" || npath < best[x][y])) {
dist[x][y] = ndist
best[x][y] = npath
heap.Push(h, State{x: x, y: y, dist: ndist, path: npath})
}
}
}
if best[hole[0]][hole[1]] == "" {
return "impossible"
}
return best[hole[0]][hole[1]]
}
复杂度分析
- 时间复杂度：设网格格数为
V = mn，一次滚动最多经过D格，候选路径最大长度为L，上界为 $O(V(D+L\log(V+1)))$。每个停点最多有四条出边，滚动需要逐格模拟，堆比较与路径构造还涉及字符串成本。- 空间复杂度：$O(VL)$，用于距离、最佳路径以及携带路径字符串的堆状态。
关键点总结
[!green]
- 图的边权是实际滚动距离，不能把一次选方向当作距离一。
- 距离相同而路径更小，同样是必须传播的改进。
- 入洞要在滚动过程中识别，不能只检查靠墙停点。
易错点总结
[!yellow]
- 只在距离减少时更新，会保留字典序更大的等距路线。
- 堆按字典序排在距离之前，会把目标变成先优化字符串而非距离。
- 只检查过期距离，不检查过期路径，会重复扩展已经被同距更小路径替代的记录。
- 不能移动时仍追加字符，会产生题目不允许的原地操作，也破坏正边权的依据。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 505. 迷宫 II | 中等 | 同样按滚动距离做最短路，本题遇洞提前停且同距离时需比较路径字符串。 |
| 490. 迷宫 | 中等 | 原题只判断可达，本题还需要最短距离与字典序两个排序条件。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！