LeetCode 1091中等网格 BFS
二进制矩阵中的最短路径 图解题解
这道题到底在问什么
给定 n×n 的二进制矩阵 grid（0 可走、1 是障碍）。一条从左上角 (0,0) 到右下角 (n-1,n-1) 的路径，每步可走 8 个方向（含斜角），路径长度 = 经过的格子数。返回最短路径长度；走不通返回 -1。
- 输入
- 5×5 矩阵，起点终点都是 0
- 输出
- 最短路径踩过的格子数
最优解：一步一步想明白
- 3记住三件事：队列先进先出保证「先到的层更短」；每个格子入队时就标已访问，绝不入队第二次；距离 = 父格子距离 + 1。下面把这趟 BFS 一格一格演给你看。
- 4起点 (0,0) 入队，距离记为 1（路径长度数格子，起点自己算 1 格）。它现在是队头。
- 5队头取出 (0,0)，距离 1。看它周围 8 格，能走又没走过的有：(1,0)，全部入队、距离记为 2，并立刻标为已访问。
- 6队头取出 (1,0)，距离 2。看它周围 8 格，能走又没走过的有：(2,0)、(2,1)，全部入队、距离记为 3，并立刻标为已访问。
- 7队头取出 (2,0)，距离 3。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 8队头取出 (2,1)，距离 3。看它周围 8 格，能走又没走过的有：(1,2)、(2,2)、(3,2)，全部入队、距离记为 4，并立刻标为已访问。
- 9队头取出 (1,2)，距离 4。看它周围 8 格，能走又没走过的有：(0,2)、(0,3)，全部入队、距离记为 5，并立刻标为已访问。
- 10队头取出 (2,2)，距离 4。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 11队头取出 (3,2)，距离 4。看它周围 8 格，能走又没走过的有：(4,1)、(4,2)，全部入队、距离记为 5，并立刻标为已访问。
- 12队头取出 (0,2)，距离 5。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 13队头取出 (0,3)，距离 5。看它周围 8 格，能走又没走过的有：(0,4)，全部入队、距离记为 6，并立刻标为已访问。
- 14队头取出 (4,1)，距离 5。看它周围 8 格，能走又没走过的有：(4,0)、(5,0)，全部入队、距离记为 6，并立刻标为已访问。
- 15队头取出 (4,2)，距离 5。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 16队头取出 (0,4)，距离 6。看它周围 8 格，能走又没走过的有：(0,5)、(1,5)，全部入队、距离记为 7，并立刻标为已访问。
- 17队头取出 (4,0)，距离 6。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 18队头取出 (5,0)，距离 6。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 19队头取出 (0,5)，距离 7。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 20队头取出 (1,5)，距离 7。看它周围 8 格，能走又没走过的有：(2,4)、(2,5)，全部入队、距离记为 8，并立刻标为已访问。
- 21队头取出 (2,4)，距离 8。看它周围 8 格，能走又没走过的有：(3,4)，全部入队、距离记为 9，并立刻标为已访问。
- 22队头取出 (2,5)，距离 8。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 23队头取出 (3,4)，距离 9。看它周围 8 格，能走又没走过的有：(4,4)、(4,5)，全部入队、距离记为 10，并立刻标为已访问。
- 24队头取出 (4,4)，距离 10。看它周围 8 格，能走又没走过的有：(5,5)，全部入队、距离记为 11，并立刻标为已访问。
- 25队头取出 (4,5)，距离 10。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
- 26队头取出 (5,5)，正好是右下角终点！BFS 一层层向外扩，第一次碰到终点的距离就是最短路径长度 = 11。
- 27BFS 结束，第一次到达右下角时记下的距离就是答案：最短路径长度 = 11 个格子。
⚠️ 容易写错的地方
✗ 错：出队时才标已访问
✓ 对：入队时就立刻标已访问
出队才标，同一个格子会被好几个邻居重复入队，队列爆炸还可能算错距离
✗ 错：只走上下左右 4 方向
✓ 对：走 8 方向（含 4 个斜角）
本题斜着走也算一步，漏掉斜角会算出偏大的路径，甚至误判走不通
✗ 错：忘了起点或终点本身是墙的情况
✓ 对：开头先判 grid[0][0] 或终点为 1 直接返回 -1
起点就是墙时根本无法出发，不判会越过这个边界
完整代码（Python / C++ / Java）
Python
from collections import deque
def shortestPathBinaryMatrix(grid):
n = len(grid)
if grid[0][0] or grid[n-1][n-1]:
return -1 # 起点或终点是墙
q = deque([(0, 0, 1)]) # (行, 列, 距离)
grid[0][0] = 1 # 标记已访问
while q:
r, c, d = q.popleft()
if r == n-1 and c == n-1:
return d # 第一次到终点即最短
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1 # 入队即标已访问
q.append((nr, nc, d+1))
return -1C++
int shortestPathBinaryMatrix(vector<vector<int>>& g){
int n = g.size();
if (g[0][0] || g[n-1][n-1]) return -1;
queue<array<int,3>> q; // {r, c, dist}
q.push({0,0,1}); g[0][0] = 1;
while (!q.empty()) {
auto [r,c,d] = q.front(); q.pop();
if (r==n-1 && c==n-1) return d;
for (int dr=-1; dr<=1; dr++)
for (int dc=-1; dc<=1; dc++) {
int nr=r+dr, nc=c+dc;
if (nr>=0&&nr<n&&nc>=0&&nc<n&&g[nr][nc]==0){
g[nr][nc]=1; q.push({nr,nc,d+1});
}
}
}
return -1;
}Java
public int shortestPathBinaryMatrix(int[][] g) {
int n = g.length;
if (g[0][0]==1 || g[n-1][n-1]==1) return -1;
Queue<int[]> q = new LinkedList<>(); // {r, c, dist}
q.add(new int[]{0,0,1}); g[0][0] = 1;
while (!q.isEmpty()) {
int[] t = q.poll();
int r=t[0], c=t[1], d=t[2];
if (r==n-1 && c==n-1) return d;
for (int dr=-1; dr<=1; dr++)
for (int dc=-1; dc<=1; dc++) {
int nr=r+dr, nc=c+dc;
if (nr>=0&&nr<n&&nc>=0&&nc<n&&g[nr][nc]==0){
g[nr][nc]=1; q.add(new int[]{nr,nc,d+1});
}
}
}
return -1;
}复杂度
时间
O(n²)
每个格子最多入队、出队一次，n×n 个格子；每格看固定的 8 个方向
空间
O(n²)
队列最多装下所有格子，加上记录已访问的标记
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二进制矩阵中的最短路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用 BFS 而不是 DFS？+
BFS 按距离逐层扩展，第一次到终点就是最短；DFS 会一条路走到底，找到的不一定最短，还要回溯比较所有路径，效率低。求最短步数优先 BFS。
为什么入队时就标记已访问，而不是出队时？+
入队即标可保证每个格子只入队一次。若等出队才标，一个格子可能被多个邻居重复入队，造成队列膨胀和重复计算。
路径长度为什么从 1 开始数而不是 0？+
本题定义路径长度是「经过的格子数」，起点自己也算一格，所以起点距离记为 1。如果数的是边数，起点才是 0。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 二进制矩阵中的最短路径 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。