LeetCode - Number of Islands（島嶼的數量）

題目描述

給定一個 m x n 的二維二進制網格 grid，其中 1 表示陸地，0 表示水。島嶼由相鄰的陸地單元格（水平或垂直相連）組成。求出網格中島嶼的數量。

範例：

輸入：
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
輸出：3
解釋：該網格中有三個島嶼。

解法思路

這個問題可以轉化為找連通分量的問題，可以使用深度優先搜索（DFS）或廣度優先搜索（BFS）來遍歷每個島嶼。

1. 遍歷網格：對每個單元格進行遍歷，當遇到 1 時，說明找到了新的島嶼，島嶼數量 count 增加。
2. DFS 或 BFS 探索整個島嶼：
   • 當遇到 1 時，啟動 DFS 或 BFS，將與此陸地連通的所有 1 都標記為 0，表示已訪問過。
   • 這樣可以保證同一個島嶼的所有陸地單元格被訪問到，避免重複計數。
3. 計數島嶼：每次啟動 DFS 或 BFS 都是新的島嶼，因此島嶼數量 count 增加。

範例代碼

以下是使用 DFS 的 Python 實現：

def numIslands(grid):
    if not grid:
        return 0

    def dfs(r, c):
        # 如果超出邊界或遇到水，則返回
        if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == "0":
            return
        # 將當前格子標記為已訪問
        grid[r][c] = "0"
        # 遍歷四個方向
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    count = 0
    # 遍歷整個網格
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            # 遇到未訪問的陸地時，執行 DFS
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)  # 標記整個島嶼

    return count

代碼解析

1. DFS 函數：對於給定的 (r, c)，將所有相鄰的 1 改為 0，避免重複訪問。
2. 遍歷網格：對於每個單元格，當遇到 1 時，啟動 DFS，並將島嶼數量 count 增加。
3. 返回結果：返回最終的島嶼數量 count。

時間和空間複雜度

• 時間複雜度：O(M * N)，其中 M 和 N 分別是網格的行數和列數。每個單元格訪問一次。
• 空間複雜度：O(M * N)，DFS 遞歸棧深度在最壞情況下可能達到整個網格的大小。