DEV Community
·
542. 01 矩阵
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定一个 m x n 的二进制矩阵，使用多源广度优先搜索（BFS）从所有 0 单元格出发，计算每个单元格到最近 0 的距离，时间复杂度为 O(m × n)。
🎯
关键要点
- 给定一个 m x n 的二进制矩阵，返回每个单元格到最近 0 的距离。
- 相邻单元格之间的距离为 1。
- 使用多源广度优先搜索（BFS）从所有 0 单元格出发。
- 对于每个 1 单元格，计算到最近 0 的最小距离。
- 初始化距离数组，所有单元格初始值为 PHP_INT_MAX，0 单元格的距离设为 0。
- 使用队列同时从所有 0 单元格进行 BFS，检查邻居并更新距离。
- 时间复杂度为 O(m × n)，空间复杂度为 O(m × n)。
➡️
