LeetCode 1293. 网格中的最短路径

2025-01-16 HGNULB 约 8 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 困难未解决 5-10 字节跳动快手百度京东亚马逊

题目描述

✅ 1293. 网格中的最短路径

题意分析

网格里每个格子要么是空地要么是障碍。从左上角出发走到右下角，每步只能上下左右挪一格，途中允许把最多 $k$ 个障碍「打通」当作空地走过去。问最少需要多少步，走不到就返回 $-1$。

「每步代价相同」这一点决定了这是无权图上的最短路问题，按步数逐层扩展即可，不需要带权最短路那套。

真正让它区别于普通网格最短路的是「打通次数」这个资源。同一个格子，带着不同的剩余次数站在上面，处境是不一样的：剩余次数多的那个未来能走通更多路。因此「是否访问过」不能只看坐标，还要看手上还剩多少额度。

数据范围里网格边长不超过 $40$，$k$ 不超过 $m \cdot n$，也就是状态总量在几万这个量级，完全允许把「坐标加剩余次数」当成状态整体搜索一遍。

边界情形包括：网格只有一个格子，起点即终点，答案为零；起点或终点周围被障碍围死且额度不够，返回 $-1$；额度大到足以直接沿直角折线穿过所有障碍，此时答案就是曼哈顿距离；以及同一个格子会被以不同剩余次数多次到达，这正是需要精细处理的地方。

解法：BFS + 剩余消除次数剪枝

核心思路

每一步代价都为 1，所以用 BFS 按步数分层搜索。难点是“剩余消除次数”会影响后续可达性：同一坐标、剩余次数不同，不能直接视为同一状态。

完整状态可写成 (row, col, remain)。进一步利用支配关系压缩状态：若同一个格子以前曾以更多或相同的 remain 到达，那么当前状态步数不会更短、资源也不更多，没有继续搜索的价值。因此用二维数组 best[row][col] 记录到达该格子时见过的最大剩余次数。

BFS 的不变量是：队列按路径长度分层；被剪掉的每个状态，都存在一个步数不更多且剩余次数不少的状态可以覆盖它的所有后续走法。因此第一次出队到达终点时，步数就是最短距离。

还有一个直接剪枝：任意曼哈顿最短路长为 rows + cols - 2，中间最多经过 rows + cols - 3 个障碍。若 k 不小于该值，可以直接返回曼哈顿距离。

解题步骤

单格网格直接返回 0；若 k 足够打通任意曼哈顿路径，直接返回曼哈顿距离。

把 best 初始化为 -1，起点记录为 k 并入队。

按层取出状态，枚举上下左右四个相邻格。

进入障碍时令 nextRemain = remain - 1；小于 0 说明资源不足。

若 nextRemain <= best[nextRow][nextCol]，当前状态被已有状态支配，跳过。

否则更新 best 并入队。队列耗尽仍未到终点则返回 -1。

代码实现

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

class Solution {
    private static final int[] DIRS = {1, 0, -1, 0, 1};

    public int shortestPath(int[][] grid, int k) {
        int rows = grid.length;
        int cols = grid[0].length;
        int distance = rows + cols - 2;
        if (distance == 0) {
            return 0;
        }
        if (k >= distance - 1) {
            return distance;
        }

        int[][] best = new int[rows][cols];
        for (int[] row : best) {
            Arrays.fill(row, -1);
        }

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0, k});
        best[0][0] = k;

        for (int steps = 0; !queue.isEmpty(); steps++) {
            for (int size = queue.size(); size > 0; size--) {
                int[] state = queue.poll();
                int row = state[0];
                int col = state[1];
                int remain = state[2];
                if (row == rows - 1 && col == cols - 1) {
                    return steps;
                }

                for (int d = 0; d < 4; d++) {
                    int nextRow = row + DIRS[d];
                    int nextCol = col + DIRS[d + 1];
                    if (nextRow < 0 || nextRow >= rows
                            || nextCol < 0 || nextCol >= cols) {
                        continue;
                    }

                    int nextRemain = remain - grid[nextRow][nextCol];
                    if (nextRemain < 0
                            || nextRemain <= best[nextRow][nextCol]) {
                        continue;
                    }

                    best[nextRow][nextCol] = nextRemain;
                    queue.offer(new int[]{nextRow, nextCol, nextRemain});
                }
            }
        }
        return -1;
    }
}

func shortestPath(grid [][]int, k int) int {
    rows, cols := len(grid), len(grid[0])
    distance := rows + cols - 2
    if distance == 0 {
        return 0
    }
    if k >= distance-1 {
        return distance
    }

    best := make([][]int, rows)
    for row := range best {
        best[row] = make([]int, cols)
        for col := range best[row] {
            best[row][col] = -1
        }
    }

    type state struct {
        row, col, remain int
    }
    dirs := [5]int{1, 0, -1, 0, 1}
    queue := []state{{row: 0, col: 0, remain: k}}
    best[0][0] = k

    for steps := 0; len(queue) > 0; steps++ {
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[i]
            if cur.row == rows-1 && cur.col == cols-1 {
                return steps
            }

            for d := 0; d < 4; d++ {
                nextRow := cur.row + dirs[d]
                nextCol := cur.col + dirs[d+1]
                if nextRow < 0 || nextRow >= rows ||
                    nextCol < 0 || nextCol >= cols {
                    continue
                }

                nextRemain := cur.remain - grid[nextRow][nextCol]
                if nextRemain < 0 ||
                    nextRemain <= best[nextRow][nextCol] {
                    continue
                }

                best[nextRow][nextCol] = nextRemain
                queue = append(queue, state{
                    row: nextRow, col: nextCol, remain: nextRemain,
                })
            }
        }
        queue = queue[size:]
    }
    return -1
}

复杂度分析

时间复杂度：$O(mnK)$，其中 $K = min(k, m+n)$。一个格子的 best 最多提升 $K+1$ 次，每次扩展四个方向。

空间复杂度：$O(mnK)$ 为队列最坏上界；best 本身只占 $O(mn)$。不能因为访问表是二维的，就忽略队列中可能同时存在同一坐标的多个资源状态。

关键点总结

路径携带可消耗资源时，资源通常必须并入搜索状态。

同坐标下“步数更少、剩余次数更多”的状态支配其他状态，可用二维最优值剪枝。

best 要在入队时更新，避免同层重复状态大量进入队列。

只有所有边权相同才能直接使用 BFS；若消除障碍有额外代价，应改用带权最短路。

k 足够大时直接返回曼哈顿距离，既是优化也是常见面试追问。

易错点总结

只按坐标标记访问：会错过“较晚到达但剩余次数更多”的有效路径。

best 初始化为 0：会误剪掉恰好用完消除次数的状态，应初始化为 -1。

剩余次数相等时仍入队：不会增加可达性，只会制造重复搜索。

忘记单格网格：起点就是终点，答案是 0。

把二维 best 误写成 $O(mn)$ 的总空间复杂度：队列仍可能保存更多状态。

相似题目

题目	难度	考察点
1091. 二进制矩阵中的最短路径	中等	同为网格最短路但障碍完全不可通行，没有资源维度，八个方向而非四个
542. 01 矩阵	中等	求每个格子到最近目标的距离，靠把所有源点一次性入队的多源扩展
1162. 地图分析	中等	同为多源扩展，但要的是所有距离中的最大值，答案在最后一层
994. 腐烂的橘子	中等	多源扩散并需统计层数，还要检验是否存在永远扩散不到的格子
909. 蛇梯棋	中等	网格被折叠成一维编号，移动规则由骰子与传送同时决定
773. 滑动谜题	困难	状态是整个棋盘的排列而非坐标，需要把状态编码成字符串再去重
752. 打开转盘锁	中等	状态是四位数字组合，额外带一份必须避开的死亡列表，适合双向扩展
LCR 109. 打开转盘锁	中等	与 752 同题异名，可用来复核状态编码与死亡列表的处理是否稳妥
127. 单词接龙	困难	状态是单词，邻居靠通配模板批量生成，建图本身就是主要开销
LCR 108. 单词接龙	困难	与 127 同题异名，适合练习双向扩展把搜索规模开方的写法
433. 最小基因变化	中等	与单词接龙同构但字符集只有四种，可直接枚举全部单点变异
854. 相似度为 K 的字符串	困难	邻居由交换操作生成，必须靠贪心只交换首个失配位来压缩分支
1345. 跳跃游戏 IV	困难	相同值的下标互为邻居，关键是用完一组后立刻清空以避免重复展开
1654. 到家的最少跳跃次数	中等	状态要附加「上一步是否后退」这一位，且需要论证坐标上界
1129. 颜色交替的最短路径	中等	状态附加「上一条边的颜色」，是本题「状态加一维」思路的另一种形态
LCP 09. 最小跳跃次数	困难	向左可达区间随扩展单调收缩，需要维护边界避免重复访问
1298. 你能从盒子里获得的最大糖果数	困难	不求最短路而求可达集合上的累计收益，钥匙与盒子互相解锁需反复重扫
LCR 107. 01 矩阵	中等	与 542 同题异名，可用来复核多源初始化与距离数组的写法