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)。
❓
延伸问答
如何计算二进制矩阵中每个单元格到最近0的距离？
使用多源广度优先搜索（BFS）从所有0单元格出发，计算每个1单元格到最近0的最小距离。
这个算法的时间复杂度和空间复杂度分别是多少？
时间复杂度为O(m × n)，空间复杂度也为O(m × n)。
在这个算法中，如何初始化距离数组？
距离数组初始化为PHP_INT_MAX，0单元格的距离设为0。
相邻单元格之间的距离是如何定义的？
相邻单元格之间的距离为1。
可以给出一个示例输入和输出吗？
输入: [[0,0,0],[0,1,0],[1,1,1]]，输出: [[0,0,0],[0,1,0],[1,2,1]]。
如何使用队列进行多源BFS？
使用队列同时从所有0单元格进行BFS，检查邻居并更新距离。
➡️
