サブアイランドを数える

1905年。サブ島を数える

難易度: 中

トピック: 配列、深さ優先検索、幅優先検索、和集合検索、行列

0 (水を表す) と 1 (土地を表す) のみを含む 2 つの m x n バイナリ行列 Grid1 と Grid2 が与えられます。 島は、4 方向 (水平または垂直) に接続された 1 のグループです。グリッドの外側にあるセルはすべて水のセルとみなされます。

グリッド 2 のこの島を構成するセルの すべてを含むグリッド 1 の島がある場合、グリッド 2 の島は サブ島とみなされます。 .

グリッド 2 内のサブアイランドと見なされるアイランドの数を返します。

例 1:

• 入力: グリッド 1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1, 0,0,0,0],[1,1,0,1,1]]、グリッド 2 = [[1,1,1,0,0],[0,0,1,1,1],[ 0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
• 出力: 3
• 説明:
  • 上の図では、左側のグリッドは Grid1 で、右側のグリッドは Grid2 です。
  • グリッド 2 で赤く塗られた 1 は、サブアイランドの一部であると考えられます。サブ島は 3 つあります。

例 2:

• 入力: グリッド 1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1, 1,1,1,1],[1,0,1,0,1]]、グリッド 2 = [[0,0,0,0,0],[1,1,1,1,1],[ 0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
• 出力: 2
• 説明:
  • 上の図では、左側のグリッドは Grid1 で、右側のグリッドは Grid2 です。
  • グリッド 2 で赤く塗られた 1 は、サブアイランドの一部であると考えられます。サブ島が 2 つあります。

制約:

• m == グリッド 1.長さ == グリッド 2.長さ
• n == グリッド1[i].length == グリッド2[i].length
• 1
• Grid1[i][j] と Grid2[i][j] は 0 または 1 です。

ヒント:

1. floodfill を使用して、2 番目のグリッドの島を反復してみましょう
2. 2 番目のグリッドの島内のすべてのセルが最初のグリッドの陸地で表されている場合、それらは接続されているため、その島がサブアイランドになることに注意してください

解決策:

深さ優先検索 (DFS) アプローチを使用してグリッド 2 のアイランドを探索し、各アイランドがグリッド 1 の対応するアイランド内に完全に含まれているかどうかを確認します。ソリューションを実装する方法は次のとおりです:

手順:

1. グリッドの走査: Grid2 の各セルを反復処理します。
2. グリッド 2 で島を特定する: グリッド 2 で陸上セル (1) に遭遇したら、DFS を使用して島全体を探索します。
3. サブアイランド条件の確認: グリッド 2 のアイランドで DFS を実行しているときに、グリッド 1 内の対応するすべてのセルも陸上セルであるかどうかを確認します。存在する場合、その島はサブアイランドです。
4. サブアイランドの数: サブアイランド条件を満たすグリッド 2 の各アイランドについて、サブアイランドの数を増やします。

このソリューションを PHP で実装してみましょう: 1905。サブ島を数える

<?php
/**
 * @param $grid1
 * @param $grid2
 * @return int
 */
function countSubIslands($grid1, $grid2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $grid1
 * @param $grid2
 * @param $i
 * @param $j
 * @param $m
 * @param $n
 * @return int|true
 */
function dfs(&$grid1, &$grid2, $i, $j, $m, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$grid1 = [
    [1,1,1,0,0],
    [0,1,1,1,1],
    [0,0,0,0,0],
    [1,0,0,0,0],
    [1,1,0,1,1]
];

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

echo countSubIslands($grid1, $grid2); // Output: 3

// Example 2
$grid1 = [
    [1,0,1,0,1],
    [1,1,1,1,1],
    [0,0,0,0,0],
    [1,1,1,1,1],
    [1,0,1,0,1]
];

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

echo countSubIslands($grid1, $grid2); // Output: 2
?>

説明：

• DFS 関数: dfs 関数は、grid2 の島を探索し、grid1 の対応するセルがすべて陸上セルであるかどうかを確認します。グリッド 2 のいずれかのセルが陸地であるが、グリッド 1 の対応するセルが水である場合、グリッド 2 の島はサブ島ではありません。
• 訪問済みとしてマーク: Grid2 を移動するときに、セルを 0 に設定して訪問済みとしてマークします。
• メインループ: Grid2 内のすべてのセルを反復処理します。訪問されていない陸上セルを見つけるたびに、DFS を開始して、それがサブアイランドの一部であるかどうかを確認します。

時間計算量:

時間計算量は (O(m x n)) です。ここで、m は行数、n は列数です。これは、すべてのセルを 1 回訪問する可能性があるためです。

このソリューションは、指定された制約内で効率的に機能するはずです。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がサブアイランドを数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。