题目描述
思路解析动画文字版
记住「状态带上剩余消除次数、best 存每格见过的最大 rem、只有更大才入队」,下面逐帧套它。
从起点 (0,0) 出发,手里有 1 次消除机会,记 best[0][0]=1、步数 0,放进队列。格子上标的 k1 就是「到这里时还剩几次消除」。
轮到队首 (0,0)(紫):此刻剩余消除次数 1、已走 0 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (1,0) 是障碍,消除它(剩余 1 减 1 = 0),记 best=0、步数 1 入队(标 k0)。
往右的 (0,1) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 1 入队(标 k1)。
轮到队首 (1,0)(紫):此刻剩余消除次数 0、已走 1 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (2,0) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 2 入队(标 k0)。
往上的 (0,0):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
往右的 (1,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
轮到队首 (0,1)(紫):此刻剩余消除次数 1、已走 1 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (1,1) 是障碍,消除它(剩余 1 减 1 = 0),记 best=0、步数 2 入队(标 k0)。
往右的 (0,2) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 2 入队(标 k1)。
往左的 (0,0):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
轮到队首 (2,0)(紫):此刻剩余消除次数 0、已走 2 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (3,0) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 3 入队(标 k0)。
往上的 (1,0) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
往右的 (2,1) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 3 入队(标 k0)。
轮到队首 (1,1)(紫):此刻剩余消除次数 0、已走 2 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (2,1):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
往上的 (0,1):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
往右的 (1,2) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 3 入队(标 k0)。
往左的 (1,0) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
轮到队首 (0,2)(紫):此刻剩余消除次数 1、已走 2 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (1,2) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 3 入队(标 k1)。
往左的 (0,1):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
轮到队首 (3,0)(紫):此刻剩余消除次数 0、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (4,0) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 4 入队(标 k0)。
往上的 (2,0):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
往右的 (3,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
轮到队首 (2,1)(紫):此刻剩余消除次数 0、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (3,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
往上的 (1,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
往右的 (2,2) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 4 入队(标 k0)。
往左的 (2,0):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
轮到队首 (1,2)(紫):此刻剩余消除次数 0、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (2,2):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
往上的 (0,2):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
往左的 (1,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
轮到队首 (1,2)(紫):此刻剩余消除次数 1、已走 3 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (2,2) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 4 入队(标 k1)。
往上的 (0,2):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
往左的 (1,1):走过去剩余 消一个后剩 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
轮到队首 (4,0)(紫):此刻剩余消除次数 0、已走 4 步。看它上下左右四个邻居,决定哪些值得走。
往上的 (3,0):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
往右的 (4,1) 是空地,剩余不变还是 0,而且比这格旧记录更优,记 best=0、步数 5 入队(标 k0)。
轮到队首 (2,2)(紫):此刻剩余消除次数 0、已走 4 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (3,2) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
往上的 (1,2):走过去剩余 还是 0,但之前到这格时剩余有 1、比现在多。剩得多的那次后劲更足,这次更差,不必再入队。
往左的 (2,1):走过去剩余 还是 0,而之前已经用同样的剩余 0 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
轮到队首 (2,2)(紫):此刻剩余消除次数 1、已走 4 步。看它上下左右四个邻居,决定哪些值得走。
往下的 (3,2) 是障碍,消除它(剩余 1 减 1 = 0),记 best=0、步数 5 入队(标 k0)。
往上的 (1,2):走过去剩余 还是 1,而之前已经用同样的剩余 1 到过这里了,这次并不更优;判重规则是只有剩余严格更大才入队,相等也要跳过。
往左的 (2,1) 是空地,剩余不变还是 1,而且比这格旧记录更优,记 best=1、步数 5 入队(标 k1)。
轮到队首 (4,1)(紫):此刻剩余消除次数 0、已走 5 步。看它上下左右四个邻居,决定哪些值得走。
往上的 (3,1) 是障碍(墙),可手里剩余消除次数已经是 0、消不动了,这个方向只能放弃。
往右就是终点 (4,2)(绿)!BFS 第一次走到终点,当前步数 5 再加这一步 = 6,就是答案。
从终点沿父指针回溯,把这条最短路点亮(绿)。它一共 6 步,中途消除了路上的障碍。回头看:正因为状态带了「剩余消除次数」、用 best 记每格见过的最大 rem,BFS 才没把「剩得多」和「剩得少」当成同一种「已访问」,从而找到真正的最短路。
边界:1×1 返回 0;k 极大退化成普通 BFS;到不了返回 −1。
两个追问:可用 (r,c,rem) 三元组 visited;等权最短路用 BFS 即可。
参考代码
from typing import Listfrom collections import dequeclass 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复杂度
- 时间：O(m·n·k)，状态总数最多是「格子数 m·n」乘「剩余次数 0..k 共 k+1 种」;每个状态只在 rem 更大时入队一次、各看 4 个邻居,所以是 O(m·n·k)
- 空间：O(m·n·k)，best 表是 O(m·n);但状态多了一维剩余次数 rem,同一格可能随不同的 rem 多次入队,队列/状态上界是 O(m·n·k),取整体最坏 O(m·n·k)
易错点
面试追问把动画讲成自己的话
追问能不能用 visited 集合存 (r,c,rem) 三元组代替 best 表?
追问为什么这题用 BFS 而不是 Dijkstra?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
跳跃游戏 IV
LeetCode 1345 · 困难 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题