200. Number of Islands

Medium

Description

給定一個 m x n 的二維網格 grid，其中 '1' 代表陸地、'0' 代表水域。計算島嶼的數量。島嶼被水域包圍，由相鄰（水平或垂直）的陸地連接而成。

Example:

Input: grid = [[“1”,“1”,“0”,“0”,“0”],[“1”,“1”,“0”,“0”,“0”],[“0”,“0”,“1”,“0”,“0”],[“0”,“0”,“0”,“1”,“1”]] Output: 3

Intuition#

每找到一個未訪問的 ‘1’，就代表發現一座新島嶼，用 DFS/BFS 把整座島標記為已訪問。

遍歷整個網格，遇到 '1' 就啟動搜尋，將相連的所有 '1' 標記為已訪問
每次啟動搜尋代表找到一座新島嶼，計數器加一
可以用 DFS、BFS 或 Union-Find 三種方式實作

Approaches#

1: BFS#

概念: 遇到 '1' 時，用 BFS 展開，將所有相連的 '1' 改為 '0'（原地標記避免額外空間）
時間複雜度: O(m * n)
空間複雜度: O(min(m, n))（BFS 佇列最大寬度）

class Solution {
    fun numIslands(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var count = 0
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == '1') {
                    count++
                    grid[i][j] = '0'
                    val queue: ArrayDeque<Int> = ArrayDeque()
                    queue.add(i * n + j)
                    while (queue.isNotEmpty()) {
                        val cur = queue.removeFirst()
                        val r = cur / n
                        val c = cur % n
                        for (d in 0 until 4) {
                            val nr = r + dirs[d]
                            val nc = c + dirs[d + 1]
                            if (nr in 0 until m && nc in 0 until n && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0'
                                queue.add(nr * n + nc)
                            }
                        }
                    }
                }
            }
        }
        return count
    }
}

⭐2: DFS（原地標記）#

概念: 遇到 '1' 時，用遞迴 DFS 將所有相連的 '1' 改為 '0'，程式碼最簡潔
時間複雜度: O(m * n)
空間複雜度: O(m * n)（遞迴呼叫堆疊最壞情況）

class Solution {
    fun numIslands(grid: Array<CharArray>): Int {
        var count = 0
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if (grid[i][j] == '1') {
                    count++
                    dfs(grid, i, j)
                }
            }
        }
        return count
    }

    private fun dfs(grid: Array<CharArray>, i: Int, j: Int) {
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] != '1') return
        grid[i][j] = '0'
        dfs(grid, i + 1, j)
        dfs(grid, i - 1, j)
        dfs(grid, i, j + 1)
        dfs(grid, i, j - 1)
    }
}

補充解法：Union-Find

概念: 將所有 '1' 格子初始化為獨立集合，相鄰的 '1' 進行 union，最終集合數即島嶼數
時間複雜度: O(m * n * α(m * n))（近似線性）
空間複雜度: O(m * n)

class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray
    private var count = 0

    fun numIslands(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        parent = IntArray(m * n)
        rank = IntArray(m * n)
        count = 0

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == '1') {
                    parent[i * n + j] = i * n + j
                    count++
                }
            }
        }

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == '1') {
                    if (i + 1 < m && grid[i + 1][j] == '1') union(i * n + j, (i + 1) * n + j)
                    if (j + 1 < n && grid[i][j + 1] == '1') union(i * n + j, i * n + j + 1)
                }
            }
        }
        return count
    }

    private fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    private fun union(x: Int, y: Int) {
        val px = find(x)
        val py = find(y)
        if (px == py) return
        if (rank[px] < rank[py]) parent[px] = py
        else if (rank[px] > rank[py]) parent[py] = px
        else { parent[py] = px; rank[px]++ }
        count--
    }
}

🔑 Takeaways#

Pattern: 網格連通性問題 – DFS/BFS 遍歷 + 原地標記
關鍵技巧: 將格子直接改為 '0' 省去 visited 陣列；座標編碼 i * n + j 用於 BFS 佇列或 Union-Find