。矩阵

542。 01 矩阵

难度：中等

主题：数组、动态规划、广度优先搜索、矩阵

给定一个 m x n 二进制矩阵 mat，返回每个单元格最近的 0 的距离。

共享公共边的两个单元格之间的距离为 1。

示例1：

• 输入： mat = [[0,0,0],[0,1,0],[0,0,0]]
• 输出： [[0,0,0],[0,1,0],[0,0,0]]

示例2：

• 输入： mat = [[0,0,0],[0,1,0],[1,1,1]]
• 输出： [[0,0,0],[0,1,0],[1,2,1]]

约束：

• m == mat.length
• n == mat[i].length
• 1 4
• 1 4
• mat[i][j] 为 0 或 1。
• mat中至少有一个0。

注：此题与1765相同。最高峰地图

解决方案：

我们将使用多源广度优先搜索（BFS），其中所有 0 个单元格都被视为起点（源）。对于每 1 个单元格，我们计算到最接近的 0 的最小距离。

让我们用 PHP 实现这个解决方案：542。 01 矩阵

<?php /**
 * @param Integer[][] $mat
 * @return Integer[][]
 */
function updateMatrix($mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$mat1 = [[0,0,0],[0,1,0],[0,0,0]];
$mat2 = [[0,0,0],[0,1,0],[1,1,1]];

echo updateMatrix($mat1) . "\n"; // Output: [[0,0,0],[0,1,0],[0,0,0]]
echo updateMatrix($mat2) . "\n"; // Output: [[0,0,0],[0,1,0],[1,2,1]]
?>

解释：

1. 初始化：

   • 所有单元格的距离数组最初使用 PHP_INT_MAX 进行初始化。
   • 距离数组中所有 0 个单元格都设置为 0 并添加到 BFS 队列中。

2. 多源 BFS：

   • 使用队列，我们​​同时对所有 0 个单元执行 BFS。
   • 对于队列中的每个单元格，检查其邻居（上、下、左、右）。
   • 如果邻居的距离可以减小（distance[newRow][newCol] > currentDistance 1），则更新其距离并将其入队。

3. 输出：

   • 距离数组更新为所有单元格到最接近 0 的最小距离。

输入和输出：

输入1：

$mat1 = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

输出 1：

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )
)

输入2：

$mat2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];

输出 2：

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 1
        )
)

该解决方案非常高效，时间复杂度为 O(m × n)，因为每个单元格都被处理一次。由于距离数组和 BFS 队列，空间复杂度也是 O(m × n)。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。矩阵的详细内容。更多信息请关注PHP中文网其他相关文章！