200. Number of Islands

──────────────────────────────────────────────────────────────────────

給一個由 '1'（陸地）和 '0'（水）組成的二維網格，算出有幾座島。上下左右相連的陸地算同一座島。

思路

這一題的重點在於於圖形中，進行深度優先搜索或是廣度優先搜索的遍歷。

第一步是把網格翻譯成圖：每一格是一個節點，上下左右相鄰的兩格之間有一條邊。翻譯完之後，「有幾座島」就是「這張圖有幾個連通分量」—— 一個標準的圖論問題。網格題幾乎都可以這樣翻譯，翻譯完就不必再把它當成「格子」來想。

今天的題目條件在於，如果一個陸地屬於一個島嶼的話，那該陸地一定是與其他陸地的四個方向之一有相連。要計算出有幾個島嶼，我只要站在島嶼上的任何一塊陸地，把該島嶼全部都標記成已經造訪過，那我就可以確定這個島嶼已經造訪完畢，計數器加一，接著再繼續找到下一個尚未被標記的陸地即可。

所以外層是一個雙重迴圈掃過整個網格，只有踩到「還沒被標記的陸地」時才計數 +1，然後立刻把整座島淹掉。淹掉這件事用 DFS 或 BFS 都可以，這也是為什麼這題是練這兩種遍歷的招牌題。

兩個容易忽略的點

一、可以直接改 grid 當作 visited 嗎？

把走過的陸地改成 '#'，就不用另外開一個 $O (m n)$ 的 visited 集合 —— 但代價是破壞了輸入資料。呼叫端如果還要用原本的網格就不能這樣做，那就多開一個 visited 集合，其他邏輯完全一樣。

二、BFS 要在「入列」時標記，不是「出列」時。

這是網格 BFS 最經典的 bug。如果只在出列時才標記，同一格可能被好幾個鄰居各自加進佇列一次，佇列會膨脹、時間退化。下面的 BFS 版本在 queue.append 的同一個 if 裡就把格子改成 '#'，就是為了這件事。

解題方向

深度優先搜索

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        
        def dfs(row, col):
            grid[row][col] = '#'
            for dr, dc in directions:
                next_row = row+dr
                next_col = col+dc
                if 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == '1':
                    dfs(next_row, next_col)
                    
        islands = 0
        
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '1':
                    islands += 1
                    dfs(row, col)
                    
        return islands

directions 這個方向陣列是網格題的固定寫法，比展開成四段 if 好讀得多，而且要改成八方向（含對角線）只要多加四組。

遞迴深度等於島的大小，最壞情況是整張網格都是陸地。這題的網格上限是 300×300 = 90000 格，而 Python 預設的遞迴上限是 1000 —— 整張網格都是陸地時遞迴深度就是 90000，遠遠超過預設值（判題環境通常會調高）。這是 BFS 版在最壞情況下比較安全的原因。

廣度優先搜索

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        islands = 0
        
        def bfs(i, j):
            queue = deque([(i, j)])
            while queue:
                row, col = queue.popleft()
                grid[row][col] = '#'
                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == "1":
                        queue.append((new_row, new_col))
                        grid[new_row][new_col] = '#'

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    islands += 1
                    bfs(i, j)
                    
        return islands

注意 queue.append(...) 下面緊接著就是 grid[new_row][new_col] = '#' —— 這就是上面說的「入列即標記」。

BFS 版沒有遞迴，不會爆堆疊，所以網格很大時 BFS 才是安全的選擇。

補充

Union-Find 也能解這題（把每塊陸地和它的右邊、下面合併，最後數有幾個集合），但我沒有用這個角度寫過這題。同樣的手法見 547. Number of Provinces 和 323. Number of Connected Components。

同一個骨架的網格題：

695. Max Area of Island —— 不是數島，而是回傳每座島的大小取最大
1992. Find All Groups of Farmland —— 回傳每塊區域的邊界座標
417. Pacific Atlantic Water Flow —— 從邊界反過來往內灌
994. Rotting Oranges、286. Walls and Gates —— 多源 BFS：一開始就把所有起點都放進佇列，這類只能用 BFS，因為要的是最短時間

骨架整理見 BFS / DFS 模板。

複雜度

深度優先搜索

時間 $O (m n)$ — 每一格最多被造訪一次（造訪後就變成 '#'，不會再進去）
空間 $O (m n)$ — 遞迴堆疊；最壞情況（整張網格都是陸地）深度等於格子數

廣度優先搜索

時間 $O (m n)$ — 同上，每格進出佇列各一次
空間 $O (\min (m, n))$ — 佇列裡最多裝下 BFS 波前的寬度，在網格上是 $O (\min (m, n))$

其中 m、n 是網格的列數和行數。

兩者時間相同，差別在空間，而且 DFS 的那個 $O (m n)$ 是真的會炸的（見上面的 RecursionError）。面試時可以先寫 DFS 因為比較短，但要主動說「如果網格很大我會改成 BFS，避免遞迴深度問題」。