計數子島

1905 年。計算子島嶼

難度：中

主題：陣列、深度優先搜尋、廣度優先搜尋、並集查找、矩陣

給定兩個 m x n 二進位矩陣 grid1 和 grid2，其中僅包含 0（代表水）和 1（代表土地）。 島嶼是一組由1連接的4向（水平或垂直）。網格之外的任何細胞都被視為水細胞。

如果grid1 中的一個島包含所有構成grid2 中這個島的單元格，則grid2 中的島被視為子島 .

返回grid2中被視為子島的數量個島嶼。

範例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]]
• 輸出： 3
• 說明：
  • 上圖中，左邊的網格是grid1，右邊的網格是grid2。
  • grid2 中紅色的 1 被認為是子島的一部分。共有三個子島。

範例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]]
• 輸出： 2
• 說明：
  • 上圖中，左邊的網格是grid1，右邊的網格是grid2。
  • grid2 中紅色的 1 被認為是子島的一部分。有兩個子島。

約束：

• m == grid1.length == grid2.length
• n == grid1[i].length == grid2[i].length
• 1
• grid1[i][j] 和 grid2[i][j] 為 0 或 1。

提示：

1. 讓我們使用洪水填充來迭代第二個網格的島嶼
2. 讓我們注意，如果第二個網格中的一個島上的所有單元格都由第一個網格中的土地表示，那麼它們就會連接起來，從而使該島成為一個子島

解：

我們將使用深度優先搜尋 (DFS) 方法來探索 grid2 中的島嶼，並檢查每個島嶼是否完全包含在 grid1 中的相應島嶼中。以下是我們如何實作該解決方案：

步驟：

1. 遍歷網格：我們將迭代 grid2 中的每個單元格。
2. 辨識 grid2 中的島嶼：當我們在 grid2 中遇到陸地單元 (1) 時，我們將使用 DFS 探索整個島嶼。
3. 檢查子島情況： 在 grid2 中的一個島嶼上執行 DFS 時，我們將檢查 grid1 中所有對應的單元格是否也是陸地單元格。如果是的話，該島就是一個子島。
4. 計算子島數： 對於 grid2 中滿足子島條件的每個島嶼，我們將增加子島數。

讓我們用 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 中對應的單元格是否都是陸地單元格。如果 grid2 中的任何單元格是陸地，但 grid1 中對應的單元格是水，則 grid2 中的島嶼不是子島。
• 標記已存取： 當我們遍歷 grid2 時，我們透過將儲存格設為 0 將其標記為已存取。
• 主循環：我們迭代grid2中的所有單元格。每當我們發現一個尚未訪問過的陸地單元時，我們都會啟動 DFS 來檢查它是否是子島的一部分。

時間複雜度：

時間複雜度為 (O(m × n))，其中 m 是行數，n 是列數。這是因為我們可能會訪問每個單元格一次。

該解決方案應該在給定的限制內有效地工作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是計數子島的詳細內容。更多資訊請關注PHP中文網其他相關文章！