题目描述
思路解析动画文字版
记住「队头取格 → 扩四邻 → 空地入队、食物即止」，第一次到食物就是最短。下面每帧扩一个格。
BFS 开始：起点 *（紫，正在处理）入队即标记已访问，步数 0。食物 # 在右下角，开始一圈圈往外扩。
出队 (0,0) · 步数 0：队头取出 (0,0)（紫，步数 0），看四邻：新空地邻居 (1,0)、(0,1) 入队即标蓝（已访问），步数记 1。
出队 (1,0) · 步数 1：队头取出 (1,0)（紫，步数 1），看四邻：新空地邻居 (2,0) 入队即标蓝（已访问），步数记 2。
出队 (0,1) · 步数 1：队头取出 (0,1)（紫，步数 1），看四邻：新空地邻居 (0,2) 入队即标蓝（已访问），步数记 2。
出队 (2,0) · 步数 2：队头取出 (2,0)（紫，步数 2），看四邻：新空地邻居 (3,0) 入队即标蓝（已访问），步数记 3。
出队 (0,2) · 步数 2：队头取出 (0,2)（紫，步数 2），看四邻：新空地邻居 (1,2)、(0,3) 入队即标蓝（已访问），步数记 3。
出队 (3,0) · 步数 3：队头取出 (3,0)（紫，步数 3），看四邻：新空地邻居 (4,0) 入队即标蓝（已访问），步数记 4。
出队 (1,2) · 步数 3：队头取出 (1,2)（紫，步数 3），看四邻：新空地邻居 (2,2) 入队即标蓝（已访问），步数记 4。
出队 (0,3) · 步数 3：队头取出 (0,3)（紫，步数 3），看四邻：四邻无新格，跳过。
出队 (4,0) · 步数 4：队头取出 (4,0)（紫，步数 4），看四邻：新空地邻居 (4,1) 入队即标蓝（已访问），步数记 5。
出队 (2,2) · 步数 4：队头取出 (2,2)（紫，步数 4），看四邻：新空地邻居 (2,3) 入队即标蓝（已访问），步数记 5。
出队 (4,1) · 步数 5：队头取出 (4,1)（紫，步数 5），看四邻：新空地邻居 (4,2) 入队即标蓝（已访问），步数记 6。
出队 (2,3) · 步数 5：队头取出 (2,3)（紫，步数 5），看四邻：新空地邻居 (2,4) 入队即标蓝（已访问），步数记 6。
出队 (4,2) · 步数 6：队头取出 (4,2)（紫，步数 6），看四邻：新空地邻居 (4,3) 入队即标蓝（已访问），步数记 7。
出队 (2,4) · 步数 6：队头取出 (2,4)（紫，步数 6），看四邻：新空地邻居 (3,4)、(1,4) 入队即标蓝（已访问），步数记 7。
出队 (4,3) · 步数 7：队头取出 (4,3)（紫，步数 7），看四邻：新空地邻居 (4,4) 入队即标蓝（已访问），步数记 8。
出队 (3,4) · 步数 7：队头取出 (3,4)（紫，步数 7），看四邻：四邻无新格，跳过。
出队 (1,4) · 步数 7：队头取出 (1,4)（紫，步数 7），看四邻：新空地邻居 (1,5) 入队即标蓝（已访问），步数记 8。
出队 (4,4) · 步数 8：队头取出 (4,4)（紫，步数 8），看四邻：新空地邻居 (4,5) 入队即标蓝（已访问），步数记 9。
出队 (1,5) · 步数 8：队头取出 (1,5)（紫，步数 8），看四邻：新空地邻居 (0,5)、(1,6) 入队即标蓝（已访问），步数记 9。
到达食物!步数 10：从 (4,5) 看四邻碰到食物 #，返回 9 + 1 = 10 步。逐层扩展，首次到达即最短。
最短路 · 10 步：顺着「从谁来的」回溯，绿色这条就是最短路，从起点到食物共 10 步。
边界先想清：紧邻、隔空地、被墙隔断（−1）。
面试常追问多源 BFS 与「BFS vs Dijkstra」。
参考代码
from typing import Listfrom collections import dequeclass Solution: def getFood(self, grid: List[List[str]]) -> int: if not grid or not grid[0]: return -1 m, n = len(grid), len(grid[0]) q = deque() for i in range(m): for j in range(n): if grid[i][j] == '*': q.append((i, j, 0)) grid[i][j] = 'X' while q: i, j, d = q.popleft() for di, dj in ((1,0),(-1,0),(0,1),(0,-1)): ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != 'X': if grid[ni][nj] == '#': return d + 1 grid[ni][nj] = 'X' q.append((ni, nj, d + 1)) return -1复杂度
- 时间：O(m·n)，每个格子最多入队、出队一次
- 空间：O(m·n)，队列与已访问标记
易错点
面试追问把动画讲成自己的话
追问如果有多个起点怎么办（本题只有一个 *，这是可迁移的扩展知识）？
追问BFS 和 Dijkstra 什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
迷宫中离入口最近的出口
LeetCode 1926 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题