LeetCode 505. 迷宫 II
题目描述
题意分析
球选定方向后必须一直滚到墙前或边界才能停下，要求最终停在目标格，并使总移动格数最少。一次滚动可能走过不同数量的格子，因此需要按实际移动距离比较路线。
解法：线性 Dijkstra + 滚动模拟
核心思路
[!blue]
把每个停点看作图中的节点，一次完整滚动看作一条边，边权就是移动的格数。
dist[x][y]保存目前找到的到达该停点的最短距离，used[x][y]表示这个距离已经确定，不会再被改小。Dijkstra 每轮在线性扫描中找出尚未确定、且
dist最小的停点u。由于所有边权非负，这个距离可以直接确定：如果存在更短路线，它从已确定区域进入的第一个未确定点，早已得到不大于该路线长度的距离，也就应比u更早被选中，产生矛盾。确定
u后，向四个方向分别滚动到不能前进，累计移动步数step。若到停点v的新距离dist[u] + step更小，就更新dist[v]。滚动时只对最终停点更新距离，中途经过目标格不算到达。起点距离设为 $0$，其他位置暂不可达。每轮至少确定一个新位置；找不到有限距离的候选时，剩余位置都无法到达，可以结束。最后目标距离仍为不可达标记就返回
-1，否则返回它的距离。
解题步骤
- 初始化距离表和定型表，将起点距离设为 $0$。
- 扫描全表，选择尚未定型的最小有限距离位置；没有候选就结束。
- 标记该位置已定型。每个方向都从这里出发，每合法移动一格就令
step加一，直到下一格是墙或越界。- 比较完整滚动形成的新距离，只在更短时更新停点。
- 返回终点距离，不可达时返回
-1。起点等于终点时初始距离已经是 $0$；贴墙产生的零步滚动不会改进自身距离。
代码实现
class Solution {
// 节点是可停靠的格子，边权是滚动步数。
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
int inf = Integer.MAX_VALUE / 4;
int[][] dist = new int[m][n];
boolean[][] used = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = inf;
}
}
dist[start[0]][start[1]] = 0;
int[] dx = new int[] {
1,
-1,
0,
0
};
int[] dy = new int[] {
0,
0,
1,
-1
};
for (int round = 0; round < m * n; round++) {
int bestX = -1;
int bestY = -1;
// 每轮重新选择尚未定型的最小有限距离
int bestDist = inf;
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (!used[x][y] && dist[x][y] < bestDist) {
bestDist = dist[x][y];
bestX = x;
bestY = y;
}
}
}
// 找不到有限候选时结束，不从不可达状态继续松弛
if (bestX == -1) {
break;
}
used[bestX][bestY] = true;
for (int d = 0; d < 4; d++) {
int nx = bestX;
int ny = bestY;
// 边权是整次滚动经过的格数，不是一次操作
int step = 0;
while (true) {
int tx = nx + dx[d];
int ty = ny + dy[d];
if (tx < 0 || ty < 0 || tx >= m || ty >= n || maze[tx][ty] == 1) {
break;
}
nx = tx;
ny = ty;
step++;
}
int nd = dist[bestX][bestY] + step;
// 只有真正变短才更新，零步自环不会产生改进
if (nd < dist[nx][ny]) {
dist[nx][ny] = nd;
}
}
}
int answer = dist[destination[0]][destination[1]];
if (answer >= inf) {
return -1;
}
return answer;
}
}
func shortestDistance(maze [][]int, start []int, destination []int) int {
// 节点是可停靠的格子，边权是滚动步数。
m := len(maze)
n := len(maze[0])
inf := m*n*(m+n) + 1
dist := make([][]int, m)
used := make([][]bool, m)
for i := 0; i < m; i++ {
dist[i] = make([]int, n)
used[i] = make([]bool, n)
for j := 0; j < n; j++ {
dist[i][j] = inf
}
}
dist[start[0]][start[1]] = 0
dx := []int{
1,
-1,
0,
0,
}
dy := []int{
0,
0,
1,
-1,
}
for round := 0; round < m*n; round++ {
bestX, bestY := -1, -1
// 每轮重新选择尚未定型的最小有限距离
best := inf
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if !used[x][y] && dist[x][y] < best {
best = dist[x][y]
bestX = x
bestY = y
}
}
}
// 找不到有限候选时结束，不从不可达状态继续松弛
if bestX == -1 {
break
}
used[bestX][bestY] = true
for d := 0; d < 4; d++ {
nx := bestX
ny := bestY
// 边权是整次滚动经过的格数，不是一次操作
step := 0
for {
tx := nx + dx[d]
ty := ny + dy[d]
if tx < 0 || ty < 0 || tx >= m || ty >= n || maze[tx][ty] == 1 {
break
}
nx = tx
ny = ty
step++
}
next := dist[bestX][bestY] + step
// 只有真正变短才更新，零步自环不会产生改进
if next < dist[nx][ny] {
dist[nx][ny] = next
}
}
}
answer := dist[destination[0]][destination[1]]
if answer >= inf {
return -1
}
return answer
}
复杂度分析
- 时间复杂度：$O((mn)^2)$。最多进行 $mn$ 轮，每轮扫描 $mn$ 个位置选点；滚动模拟另需 $O(mn\max(m,n))$，不超过前者。
- 空间复杂度：$O(mn)$，距离与定型表。
关键点总结
[!green]
- 最少滚动次数与最少经过格数不是同一个目标。
- 没有有限距离候选时停止，不对不可达状态做加法。
易错点总结
[!yellow]
- 用滚动次数当边权，会忽略每次滚动长度的差异；应累加实际移动格数。
- 沿普通相邻格建图，会允许中途停下。
- 发现节点就固定距离，可能错过之后更短的路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 490. 迷宫 | 中等 | 只判断可达时DFS或BFS即可，本题每次滚动长度不同，需要加权最短路。 |
| 499. 迷宫 III | 困难 | 原题进一步要求遇洞提前停，并在距离相同的路径中选字典序最小者。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！