01 矩阵:每个 1 到最近 0 的距离(LC542)
哪些公司问过
答案要点
- 把所有 0 作为多源起点同时入队,1 的距离初始化为未访问
- 按层 BFS 扩散,格子第一次被访问时的距离即最近 0 的步数
- 每个格子只入队一次,时间和空间复杂度 O(mn)
- 可直接用结果矩阵标记访问,处理越界和无 0 的边界
- 也可用两遍 DP:左上到右下、右下到左上各扫一次取最小
易错点
- 从每个 1 分别做 BFS,导致超时
- 入队时不标记访问,出队时才标记,同一格子被重复入队
- 矩阵中没有 0 时未按题意处理,距离停留在初始值
面试官常见追问
- 两遍 DP 为什么是对的?
- 如果矩阵里有障碍物不能通过呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。