网格中的最短路径(可消除障碍) 图解题解

这道题到底在问什么

输入

grid=[[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k=1

输出

6

最优解：一步一步想明白

1. 3记住「状态带上剩余消除次数、best 存每格见过的最大 rem、只有更大才入队」,下面逐帧套它。
2. 4从起点 (0,0) 出发,手里有 1 次消除机会,记 best[0][0]=1、步数 0,放进队列。格子上标的 k1 就是「到这里时还剩几次消除」。
3. 5轮到队首 (0,0)(紫):此刻剩余消除次数 1、已走 0 步。看它上下左右四个邻居,决定哪些值得走。
4. 6往下的 (1,0) 是障碍,消除它(剩余 1 减 1 = 0),记 best=0、步数 1 入队(标 k0)。
5. 7往右的 (0,1) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 1 入队(标 k1)。
6. 8轮到队首 (1,0)(紫):此刻剩余消除次数 0、已走 1 步。看它上下左右四个邻居,决定哪些值得走。
7. 9往下的 (2,0) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 2 入队(标 k0)。
8. 10往上的 (0,0):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
9. 11往右的 (1,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
10. 12轮到队首 (0,1)(紫):此刻剩余消除次数 1、已走 1 步。看它上下左右四个邻居,决定哪些值得走。
11. 13往下的 (1,1) 是障碍,消除它(剩余 1 减 1 = 0),记 best=0、步数 2 入队(标 k0)。
12. 14往右的 (0,2) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 2 入队(标 k1)。
13. 15往左的 (0,0):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
14. 16轮到队首 (2,0)(紫):此刻剩余消除次数 0、已走 2 步。看它上下左右四个邻居,决定哪些值得走。
15. 17往下的 (3,0) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 3 入队(标 k0)。
16. 18往上的 (1,0) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
17. 19往右的 (2,1) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 3 入队(标 k0)。
18. 20轮到队首 (1,1)(紫):此刻剩余消除次数 0、已走 2 步。看它上下左右四个邻居,决定哪些值得走。
19. 21往下的 (2,1):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
20. 22往上的 (0,1):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
21. 23往右的 (1,2) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 3 入队(标 k0)。
22. 24往左的 (1,0) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
23. 25轮到队首 (0,2)(紫):此刻剩余消除次数 1、已走 2 步。看它上下左右四个邻居,决定哪些值得走。
24. 26往下的 (1,2) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 3 入队(标 k1)。
25. 27往左的 (0,1):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
26. 28轮到队首 (3,0)(紫):此刻剩余消除次数 0、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
27. 29往下的 (4,0) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 4 入队(标 k0)。
28. 30往上的 (2,0):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
29. 31往右的 (3,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
30. 32轮到队首 (2,1)(紫):此刻剩余消除次数 0、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
31. 33往下的 (3,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
32. 34往上的 (1,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
33. 35往右的 (2,2) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 4 入队(标 k0)。
34. 36往左的 (2,0):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
35. 37轮到队首 (1,2)(紫):此刻剩余消除次数 0、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
36. 38往下的 (2,2):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
37. 39往上的 (0,2):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
38. 40往左的 (1,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
39. 41轮到队首 (1,2)(紫):此刻剩余消除次数 1、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
40. 42往下的 (2,2) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 4 入队(标 k1)。
41. 43往上的 (0,2):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
42. 44往左的 (1,1):走过去剩余 消一个后剩 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
43. 45轮到队首 (4,0)(紫):此刻剩余消除次数 0、已走 4 步。看它上下左右四个邻居,决定哪些值得走。
44. 46往上的 (3,0):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
45. 47往右的 (4,1) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 5 入队(标 k0)。
46. 48轮到队首 (2,2)(紫):此刻剩余消除次数 0、已走 4 步。看它上下左右四个邻居,决定哪些值得走。
47. 49往下的 (3,2) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
48. 50往上的 (1,2):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
49. 51往左的 (2,1):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
50. 52轮到队首 (2,2)(紫):此刻剩余消除次数 1、已走 4 步。看它上下左右四个邻居,决定哪些值得走。
51. 53往下的 (3,2) 是障碍,消除它(剩余 1 减 1 = 0),记 best=0、步数 5 入队(标 k0)。
52. 54往上的 (1,2):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
53. 55往左的 (2,1) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 5 入队(标 k1)。
54. 56轮到队首 (4,1)(紫):此刻剩余消除次数 0、已走 5 步。看它上下左右四个邻居,决定哪些值得走。
55. 57往上的 (3,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
56. 58往右就是终点 (4,2)(绿)!BFS 第一次走到终点,当前步数 5 再加这一步 = 6,就是答案。
57. 59从终点沿父指针回溯,把这条最短路点亮(绿)。它一共 6 步,中途消除了路上的障碍。回头看:正因为状态带了「剩余消除次数」、用 best 记每格见过的最大 rem,BFS 才没把「剩得多」和「剩得少」当成同一种「已访问」,从而找到真正的最短路。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque
class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        if m == 1 and n == 1:
            return 0
        best = [[-1] * n for _ in range(m)]
        best[0][0] = k
        q = deque([(0, 0, k, 0)])
        while q:
            r, c, rem, dist = q.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    nrem = rem - grid[nr][nc]
                    if nrem < 0:
                        continue
                    if nr == m - 1 and nc == n - 1:
                        return dist + 1
                    if nrem > best[nr][nc]:
                        best[nr][nc] = nrem
                        q.append((nr, nc, nrem, dist + 1))
        return -1

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        if (m == 1 && n == 1) return 0;
        vector<vector<int>> best(m, vector<int>(n, -1));
        queue<array<int,4>> q;
        q.push({0,0,k,0}); best[0][0] = k;
        int dirs[5] = {1,0,-1,0,1};
        while (!q.empty()) {
            auto [r, c, rem, dist] = q.front(); q.pop();
            for (int d = 0; d < 4; ++d) {
                int nr = r + dirs[d], nc = c + dirs[d+1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int nrem = rem - grid[nr][nc];
                    if (nrem < 0) continue;
                    if (nr == m - 1 && nc == n - 1) return dist + 1;
                    if (nrem > best[nr][nc]) { best[nr][nc] = nrem; q.push({nr, nc, nrem, dist + 1}); }
                }
            }
        }
        return -1;
    }
};

import java.util.*;
class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        if (m == 1 && n == 1) return 0;
        int[][] best = new int[m][n];
        for (int[] row : best) Arrays.fill(row, -1);
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0,0,k,0}); best[0][0] = k;
        int[] dirs = {1,0,-1,0,1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dirs[d], nc = cur[1] + dirs[d + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int rem = cur[2] - grid[nr][nc];
                    if (rem < 0) continue;
                    if (nr == m - 1 && nc == n - 1) return cur[3] + 1;
                    if (rem > best[nr][nc]) { best[nr][nc] = rem; q.offer(new int[]{nr, nc, rem, cur[3] + 1}); }
                }
            }
        }
        return -1;
    }
}

复杂度

面试官可能追问