01 矩阵中每个位置到最近 0 的距离
哪些公司问过
答案要点
- 多源 BFS:所有 0 同时入队作为起点,向外逐层扩散
- 1 初始化为未访问,首次访问时距离为出队格子距离加一,之后不再更新
- 每个格子只入队一次,时间和空间复杂度 O(mn)
- 也可两遍 DP:左上到右下取上、左,右下到左上取下、右,各加一取最小
- 处理空矩阵,以及不保证存在 0 时距离初值设为足够大
易错点
- 从每个 1 出发找 0,复杂度退化成平方级
- BFS 中出队时才标记访问,导致同一格子重复入队
- DP 只扫一遍,漏掉下方和右方来的更短路径
面试官常见追问
- 为什么不对每个 1 单独做 BFS?
- 如果允许八方向移动,或要求欧氏距离呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。