。マトリックス

542。 01 マトリックス

難易度: 中

トピック: 配列、動的計画法、幅優先検索、行列

m x n のバイナリ行列マットを指定すると、各セルの最も近い 0 の距離を返します。

共通のエッジを共有する 2 つのセル間の距離は 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 です。
• マットに少なくとも 1 つの 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 を同時に実行します。
   • キュー内の各セルについて、その隣接セル (上、下、左、右) をチェックします。
   • 近隣の距離を短縮できる場合 (距離[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
        )
)

このソリューションは、各セルが 1 回処理されるため、時間計算量が O(m × n) で効率的です。距離配列と BFS キューにより、空間複雑度も O(m × n) になります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。マトリックスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。