题目描述
思路解析动画文字版
关键不是背模板，而是看懂为什么这题适合网格 BFS。
1. 题面 · 0 可走 1 是墙：蓝色格是 0 可以走，绿色格是 1 障碍墙。起点 (0,0) 在橙色，终点 (2,2) 在红框；要从起点八方向移动，求到终点经过的最少格子数。
2. 为什么用 BFS：每走一步代价都是 1，是无权图。BFS 像水波一层层向外扩，第一次碰到终点时走过的步数一定最短，所以这题用 BFS 而不是 DFS。
3. 起点入队 · d=1：把起点 (0,0) 连同它的步数 1 一起放进队列，写成 (0,0,1)。同时立刻把 (0,0) 标成已访问（紫色），防止以后重复入队。
4. 弹出队头 (0,0) · 看八邻居：从队头弹出 (0,0,1)，队列暂时空了。它不是终点 (2,2)，于是检查它周围八个方向：只有右边 (0,1) 是 0 且没访问过，下、右下都是障碍 1。
5. (0,1) 入队 · d=2：把 (0,1) 标成已访问并入队，步数是父节点的 1 加 1，记为 (0,1,2)。BFS 的精髓：入队时就标已访问，每个格子最多进队一次。
6. 弹出队头 (0,1) · 看八邻居：弹出 (0,1,2)，它不是终点。看它的八邻居：左边 (0,0) 已访问跳过，右边 (0,2) 和右下 (1,2) 都是 0 且未访问，正下方 (1,1) 是障碍跳过。
7. (0,2) 和 (1,2) 入队 · d=3：(0,2) 和 (1,2) 都标已访问并入队，步数都是 2 加 1 等于 3，队列现在是 (0,2,3)、(1,2,3) 两个。注意它俩同属第 3 层，会先后被处理。
8. 弹出队头 (0,2) · 邻居全堵：弹出 (0,2,3)，不是终点。它的八邻居里：(0,1) 和 (1,2) 都已访问，(1,1) 是障碍，右边越界——没有新格子可入队。队列里还剩 (1,2,3)。
9. 弹出队头 (1,2) · 看八邻居：弹出 (1,2,3)，仍不是终点。检查它的八邻居：上方 (0,2) 已访问，左、左上是障碍，正下方 (2,2) 是 0 且未访问——这正是终点格！
10. (2,2) 入队 · d=4：把终点 (2,2) 标已访问并入队，步数 3 加 1 等于 4，记为 (2,2,4)。它现在排在队列里等待被弹出，弹出那一刻就能确认答案。
11. 弹出队头 (2,2) · 命中终点：弹出 (2,2,4)（橙色），判断 r 等于 n-1 且 c 等于 n-1 成立——到终点了！直接返回它携带的步数 4。因为 BFS 按层扩展，这就是最短路径长度。
12. 回看路径 · 逐层水波：高亮格连成最短路径 (0,0)→(0,1)→(1,2)→(2,2) 这一条；(0,2) 虽被访问但不在最短链上，仍是普通紫色。整张图只有 5 个 0 格被访问过，每格恰好入队一次。
13. 边界 · 起点或终点是墙：进 BFS 前先特判：如果起点 (0,0) 或终点 (2,2) 本身就是障碍 1，根本无路可走，直接返回 -1，不必入队。
14. 边界 · 队列空仍没到终点：另一种无解：障碍把终点彻底封死。BFS 把能到的格子全访问完，队列空了仍没弹出过终点，while 循环正常退出后返回 -1。
15. 雷区 · 标记时机与方向数：两个常踩的坑：① 必须在入队那一刻就标已访问，等弹出再标会让同一格多次入队、距离变大；② 本题是八方向（含四条对角线），高亮的 (1,2) 正是靠对角线从 (0,1) 一步到达，写成上下左右四方向会漏掉这条捷径、答案偏大。
把这句话记住，下次遇到同类题，就能更快选出方向。
参考代码
from collections import dequeclass Solution: def shortestPathBinaryMatrix(self, 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 dirs = [(a,b) for a in (-1,0,1) for b in (-1,0,1) if a or b] while q: r, c, d = q.popleft() if r == n - 1 and c == n - 1: return d for dr, dc in dirs: 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²)，BFS 每个格子最多入队一次，共 n² 个格子
- 空间复杂度：O(n²)，visited 标记 + 队列最多存 n² 个格子
可套用的代码模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
# 网格 BFS 通用检查表# 1. 定义状态/指针/容器# 2. 每轮只做一个清晰动作# 3. 更新答案并处理边界易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词接龙
LeetCode 127 · 困难 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题