01 矩阵最短距离并输出路径(LeetCode 542)
哪些公司问过
答案要点
- 多源 BFS:所有 0 同时入队作为起点,距离初始化为 0,其余为 -1
- 逐层扩展,格子首次被访问时的距离即最短距离
- 输出路径:扩展时记录前驱格子
- 从目标格子沿前驱回溯到某个 0,得到一条最短路径
- 时间、空间均为 O(mn);存在多个最近 0 时输出其中一条
易错点
- 对每个 1 单独 BFS 导致超时
- 入队时不立即标记访问,同一格子被多次入队
- 回溯方向搞反,前驱应指向离 0 更近的格子
面试官常见追问
- 为什么不从每个 1 分别做 BFS?
- 还有其他解法吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。