题目描述
思路解析动画文字版
记住三件事：队列先进先出保证「先到的层更短」；每个格子入队时就标已访问，绝不入队第二次；距离 = 父格子距离 + 1。下面把这趟 BFS 一格一格演给你看。
起点 (0,0) 入队，距离记为 1（路径长度数格子，起点自己算 1 格）。它现在是队头。
队头取出 (0,0)，距离 1。看它周围 8 格，能走又没走过的有：(1,0)，全部入队、距离记为 2，并立刻标为已访问。
队头取出 (1,0)，距离 2。看它周围 8 格，能走又没走过的有：(2,0)、(2,1)，全部入队、距离记为 3，并立刻标为已访问。
队头取出 (2,0)，距离 3。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (2,1)，距离 3。看它周围 8 格，能走又没走过的有：(1,2)、(2,2)、(3,2)，全部入队、距离记为 4，并立刻标为已访问。
队头取出 (1,2)，距离 4。看它周围 8 格，能走又没走过的有：(0,2)、(0,3)，全部入队、距离记为 5，并立刻标为已访问。
队头取出 (2,2)，距离 4。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (3,2)，距离 4。看它周围 8 格，能走又没走过的有：(4,1)、(4,2)，全部入队、距离记为 5，并立刻标为已访问。
队头取出 (0,2)，距离 5。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (0,3)，距离 5。看它周围 8 格，能走又没走过的有：(0,4)，全部入队、距离记为 6，并立刻标为已访问。
队头取出 (4,1)，距离 5。看它周围 8 格，能走又没走过的有：(4,0)、(5,0)，全部入队、距离记为 6，并立刻标为已访问。
队头取出 (4,2)，距离 5。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (0,4)，距离 6。看它周围 8 格，能走又没走过的有：(0,5)、(1,5)，全部入队、距离记为 7，并立刻标为已访问。
队头取出 (4,0)，距离 6。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (5,0)，距离 6。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (0,5)，距离 7。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (1,5)，距离 7。看它周围 8 格，能走又没走过的有：(2,4)、(2,5)，全部入队、距离记为 8，并立刻标为已访问。
队头取出 (2,4)，距离 8。看它周围 8 格，能走又没走过的有：(3,4)，全部入队、距离记为 9，并立刻标为已访问。
队头取出 (2,5)，距离 8。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (3,4)，距离 9。看它周围 8 格，能走又没走过的有：(4,4)、(4,5)，全部入队、距离记为 10，并立刻标为已访问。
队头取出 (4,4)，距离 10。看它周围 8 格，能走又没走过的有：(5,5)，全部入队、距离记为 11，并立刻标为已访问。
队头取出 (4,5)，距离 10。周围 8 格要么是墙、要么越界、要么已访问，没有新格子可入队，这一格到此为止。
队头取出 (5,5)，正好是右下角终点！BFS 一层层向外扩，第一次碰到终点的距离就是最短路径长度 = 11。
BFS 结束，第一次到达右下角时记下的距离就是答案：最短路径长度 = 11 个格子。
三个高频追问：选 BFS 的理由、入队即标访问、距离从 1 起算。
参考代码
from collections import dequedef 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 -1复杂度
- 时间：O(n²)，每个格子最多入队、出队一次，n×n 个格子；每格看固定的 8 个方向
- 空间：O(n²)，队列最多装下所有格子，加上记录已访问的标记
易错点
面试追问把动画讲成自己的话
追问为什么用 BFS 而不是 DFS？
追问为什么入队时就标记已访问，而不是出队时？
追问路径长度为什么从 1 开始数而不是 0？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
颜色交替的最短路径
LeetCode 1129 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题