LeetCode 题解工作台
网格中的最短路径
给你一个 m * n 的网格，其中每个单元格不是 0 （空）就是 1 （障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。 如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
class Solution: def shortestPath(self, grid: List[List[int]], k: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。
示例 1：
输入： grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
示例 2：
输入：grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 输出：-1 解释：我们至少需要消除两个障碍才能找到这样的路径。
提示：
grid.length == mgrid[0].length == n1 <= m, n <= 401 <= k <= m*ngrid[i][j]是0或1grid[0][0] == grid[m-1][n-1] == 0
解题思路
方法一
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 3:
return m + n - 2
q = deque([(0, 0, k)])
vis = {(0, 0, k)}
ans = 0
while q:
ans += 1
for _ in range(len(q)):
i, j, k = q.popleft()
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if x == m - 1 and y == n - 1:
return ans
if grid[x][y] == 0 and (x, y, k) not in vis:
q.append((x, y, k))
vis.add((x, y, k))
if grid[x][y] == 1 and k > 0 and (x, y, k - 1) not in vis:
q.append((x, y, k - 1))
vis.add((x, y, k - 1))
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on BFS's exploration of the grid, which is O(m * n * k), where m is the number of rows, n is the number of columns, and k is the maximum number of obstacles that can be eliminated. Space complexity is O(m * n * k) for storing visited states and the BFS queue. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate identify the correct algorithm pattern (BFS)?
- question_mark
Does the candidate understand the importance of managing obstacle eliminations during pathfinding?
- question_mark
Is the candidate able to optimize BFS by utilizing an efficient state-tracking mechanism?
常见陷阱
外企场景- error
Overcomplicating the problem with unnecessary algorithms or search techniques that don't account for obstacle eliminations efficiently.
- error
Failing to properly track the state of eliminated obstacles, leading to redundant processing of paths.
- error
Not leveraging BFS optimally, causing excessive computation or incorrect answers when paths with fewer eliminated obstacles are possible.
进阶变体
外企场景- arrow_right_alt
Allowing more than k obstacles to be eliminated.
- arrow_right_alt
Handling edge cases with very small grids (1x1 or 2x2).
- arrow_right_alt
Expanding the problem to work with more complex movement rules, such as diagonal movement.