LeetCode 题解工作台
到达角落需要移除障碍物的最小数目
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一： 0 表示一个 空 单元格， 1 表示一个可以移除的 障碍物 。 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, …
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
本题实际上也是最短路模型，只不过求解的是移除障碍物的最小数目。 在一个边权只有 , 的无向图中搜索最短路径可以使用双端队列进行 。其原理是当前可以扩展到的点的权重为 时，将其加入队首；权重为 时，将其加入队尾。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：
0表示一个 空 单元格，1表示一个可以移除的 障碍物 。
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。
示例 1：
输入：grid = [[0,1,1],[1,1,0],[1,1,0]] 输出：2 解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。 可以证明我们至少需要移除两个障碍物，所以返回 2 。 注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。
示例 2：
输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] 输出：0 解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j]为0或1grid[0][0] == grid[m - 1][n - 1] == 0
解题思路
方法一：双端队列 BFS
本题实际上也是最短路模型，只不过求解的是移除障碍物的最小数目。
在一个边权只有 , 的无向图中搜索最短路径可以使用双端队列进行 。其原理是当前可以扩展到的点的权重为 时，将其加入队首；权重为 时，将其加入队尾。
如果某条边权值为 ，那么新拓展出的节点权值就和当前队首节点权值相同，显然可以作为下一次拓展的起点。
时间复杂度 ，空间复杂度 。其中 和 分别是网格的行数和列数。
相似题目：
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque([(0, 0, 0)])
vis = set()
dirs = (-1, 0, 1, 0, -1)
while 1:
i, j, k = q.popleft()
if i == m - 1 and j == n - 1:
return k
if (i, j) in vis:
continue
vis.add((i, j))
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if grid[x][y] == 0:
q.appendleft((x, y, k))
else:
q.append((x, y, k + 1))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m \cdot n) because each cell is processed at most once in BFS. Space complexity is O(m \cdot n) to store the minimum removals matrix and the BFS queue or deque. |
| 空间 | O(m \cdot n) |
面试官常问的追问
外企场景- question_mark
Check if the candidate models grid as a graph with weighted edges.
- question_mark
Look for correct BFS prioritization by obstacle count.
- question_mark
Watch for handling visited states to avoid revisiting higher-cost paths.
常见陷阱
外企场景- error
Treating all moves equally instead of assigning cost to obstacles.
- error
Revisiting cells without checking if a path with fewer removals exists.
- error
Failing to handle edge cases where the start or end is surrounded by obstacles.
进阶变体
外企场景- arrow_right_alt
Compute the minimum obstacles removal for multiple target cells instead of a single corner.
- arrow_right_alt
Allow diagonal moves and adjust BFS weights accordingly.
- arrow_right_alt
Return one actual path along with the minimum obstacle count.