。矩陣

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中文網其他相關文章！