面试题库 › 音视频 › 01 矩阵中每个位置到最近 0 的距离

01 矩阵中每个位置到最近 0 的距离

难度 ★★☆在 1 场真实面经中被问到 方向:音视频考点:图论

哪些公司问过

哔哩哔哩1

常见岗位:音视频开发

答案要点

  1. 多源 BFS:所有 0 同时入队作为起点,向外逐层扩散
  2. 1 初始化为未访问,首次访问时距离为出队格子距离加一,之后不再更新
  3. 每个格子只入队一次,时间和空间复杂度 O(mn)
  4. 也可两遍 DP:左上到右下取上、左,右下到左上取下、右,各加一取最小
  5. 处理空矩阵,以及不保证存在 0 时距离初值设为足够大

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题