島嶼問題 (Number of Islands)#
經典題目：島嶼數量 ↗#
題目：給定二維網格，'1' 為陸地，'0' 為水域。計算島嶼數量。
規則：四連通（上下左右），對角線不算相連。
輸入：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
輸出：3（三個島嶼）染色法 (Flood Fill)#
核心思想#
發現一座島嶼時，將其「沉沒」（標記為已訪問），避免重複計算。
演算法步驟#
- 走訪整個網格
- 遇到
'1'時，島嶼數量 +1 - 用 DFS/BFS 將整座島嶼標記為
'0'
DFS 實作
fun numIslands(grid: Array<CharArray>): Int {
if (grid.isEmpty()) return 0
val rows = grid.size
val cols = grid[0].size
var count = 0
fun dfs(r: Int, c: Int) {
// 邊界檢查 + 是否為陸地
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return
grid[r][c] = '0' // 沉島
// 四個方向擴散
dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)
}
for (r in 0 until rows) {
for (c in 0 until cols) {
if (grid[r][c] == '1') {
count++
dfs(r, c)
}
}
}
return count
}方向陣列技巧：使用
dx = [-1, 1, 0, 0],dy = [0, 0, -1, 1]簡化四方向走訪。
副作用：直接修改 grid 會破壞原始資料。若不允許修改，需使用額外的
visited陣列。
並查集 (Union-Find)#
核心思想#
將相鄰的陸地合併到同一集合，最終集合數量即為島嶼數量。
演算法步驟#
- 初始化：每個
'1'單獨成集 - 走訪網格：相鄰的
'1'執行 Union - 統計最終集合數量
關鍵實作#
class UnionFind(n: Int) {
private val parent = IntArray(n) { it }
var count = 0
fun find(x: Int): Int {
if (parent[x] != x) {
parent[x] = find(parent[x]) // 路徑壓縮
}
return parent[x]
}
fun union(x: Int, y: Int) {
val rootX = find(x)
val rootY = find(y)
if (rootX != rootY) {
parent[rootX] = rootY
count-- // 合併時計數減 1
}
}
}座標轉換：2D 座標
(i, j)轉為 1D 索引：i * cols + j
兩種解法比較#
| 特性 | Flood Fill | Union-Find |
|---|---|---|
| 時間複雜度 | O(M × N) | O(M × N × α) |
| 空間複雜度 | O(M × N) 遞迴堆疊 | O(M × N) |
| 是否修改原圖 | 是（可避免） | 否 |
| 適用場景 | 一次性查詢 | 動態連通性 |
選擇建議：
- 簡單題目 ➡️ Flood Fill（程式碼簡潔）
- 需要多次查詢連通性 ➡️ Union-Find
變體：朋友圈 ↗#
題目：N×N 鄰接矩陣表示 N 人的好友關係，求朋友圈數量。
本質：與島嶼問題相同，都是求連通分量數量。
差異：
- 島嶼問題：網格上的空間相鄰
- 朋友圈：節點間的邏輯連接
fun findCircleNum(m: Array<IntArray>): Int {
val n = m.size
val uf = UnionFind(n)
uf.count = n // 初始每人獨立
for (i in 0 until n) {
for (j in i + 1 until n) {
if (m[i][j] == 1) {
uf.union(i, j)
}
}
}
return uf.count
}