給定一個
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
TIP
每找到一個未訪問的 ‘1’，就代表發現一座新島嶼，用 DFS/BFS 把整座島標記為已訪問。
- 遍歷整個網格，遇到
'1'就啟動搜尋，將相連的所有'1'標記為已訪問 - 每次啟動搜尋代表找到一座新島嶼，計數器加一
- 可以用 DFS、BFS 或 Union-Find 三種方式實作
Approaches
1. BFS — O(m * n) / O(min(m, n))
- Idea: 遇到
'1'時，用 BFS 展開，將所有相連的'1'改為'0'（原地標記避免額外空間） - Time:
O(m * n) - Space:
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 (in-place marking) — O(m * n) / O(m * n)
- Idea: 遇到
'1'時，用遞迴 DFS 將所有相連的'1'改為'0'，程式碼最簡潔 - Time:
O(m * n) - Space:
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)
}
}Alternative: Union-Find
- Idea: 將所有
'1'格子初始化為獨立集合，相鄰的'1'進行 union，最終集合數即島嶼數 - Time:
O(m * n * α(m * n))（近似線性） - Space:
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 遍歷 + 原地標記
- Key trick: 將格子直接改為
'0'省去 visited 陣列；座標編碼i * n + j用於 BFS 佇列或 Union-Find