LeetCode 题解工作台
二进制矩阵中的最短路径
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即， (0, 0) ）到 右下角 单元格（即， (n - 1, n - 1) ）的路径，该路径同时满足下述要求： 路径途经的所…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
根据题目描述，一条畅通路径是从左上角单元格 $(0, 0)$ 到右下角单元格 $(n - 1, n - 1)$ 的路径，且路径上所有单元格的值都是 。 因此，如果左上角单元格 $(0, 0)$ 的值为 ，则不存在满足要求的路径，直接返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
- 路径途经的所有单元格的值都是
0。 - 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。
示例 1：
输入：grid = [[0,1],[1,0]] 输出：2
示例 2：
输入：grid = [[0,0,0],[1,1,0],[1,1,0]] 输出：4
示例 3：
输入：grid = [[1,0,0],[1,1,0],[1,1,0]] 输出：-1
提示：
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]为0或1
解题思路
方法一：BFS
根据题目描述，一条畅通路径是从左上角单元格 到右下角单元格 的路径，且路径上所有单元格的值都是 。
因此，如果左上角单元格 的值为 ，则不存在满足要求的路径，直接返回 。
否则，我们创建一个队列 ，将左上角单元格 加入队列，并且将其标记为已访问，即把 的值置为 ，然后开始广度优先搜索。
在每一轮搜索中，我们每次取出队首节点 ，如果 为右下角单元格 ，则路径长度为当前的搜索轮数，直接返回。否则，我们将当前节点的所有未被访问过的相邻节点加入队列，并且将它们标记为已访问。每一轮搜索结束后，我们将搜索轮数增加 。然后继续执行上述过程，直到队列为空或者找到目标节点。
如果在搜索结束后，我们仍然没有到达右下角的节点，那么说明右下角的节点不可达，返回 。
时间复杂度 ，空间复杂度 。其中 是给定的二进制矩阵的边长。
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0]:
return -1
n = len(grid)
grid[0][0] = 1
q = deque([(0, 0)])
ans = 1
while q:
for _ in range(len(q)):
i, j = q.popleft()
if i == j == n - 1:
return ans
for x in range(i - 1, i + 2):
for y in range(j - 1, j + 2):
if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
grid[x][y] = 1
q.append((x, y))
ans += 1
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) because each cell can be visited at most once in BFS. Space complexity is O(n^2) for the queue and visited tracking, which grows with matrix size. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on BFS rather than DFS to guarantee minimal path length.
- question_mark
Check early for blocked start or end cells to avoid unnecessary computation.
- question_mark
Consider all 8 movement directions and ensure proper bounds checking.
常见陷阱
外企场景- error
Forgetting to count the starting cell in the path length.
- error
Not handling diagonal movements correctly, leading to wrong path lengths.
- error
Revisiting cells and overcounting path lengths, missing BFS shortest-path guarantee.
进阶变体
外企场景- arrow_right_alt
Compute the shortest path in a rectangular m x n binary matrix instead of square.
- arrow_right_alt
Allow only 4-directional movement to simplify BFS but change minimal path results.
- arrow_right_alt
Return all shortest paths rather than just the length, adding tracking of paths.