827. Making A Large Island
解題說明
Making A Large Island
題目描述:給定一個 n × n 的二進位網格,其中 0 代表水,1 代表陸地。最多可以將一個 0 翻轉為 1,求翻轉後最大的島嶼面積(上下左右相鄰的陸地屬於同一島嶼)。
解題思路:
暴力法:對每個 0 嘗試翻轉後 BFS/DFS 計算最大島嶼,時間複雜度 O(n⁴),太慢。
最優方案分兩個階段:
第一階段:島嶼染色 + 面積記錄
- 用 Union-Find(或 DFS)為每個島嶼分配唯一 ID(從 2 開始,避免與 0/1 混淆)。
- 維護
area[]陣列,area[id]記錄該島嶼的根節點對應的面積(即連通分量大小)。 - 遍歷所有格子,對值為
1的格子嘗試與右方和下方的1進行 union,每次 union 成功則更新根節點的面積。
第二階段:枚舉翻轉點
- 對每個值為
0的格子,檢查其四個相鄰格。 - 用
set收集四鄰中不同島嶼 ID 的根節點,對這些不同根的面積求和再 +1(翻轉本格)。 - 取所有
0格的最大值與第一階段得到的最大島嶼面積取最大值(防止全是陸地的特殊情況)。
關鍵細節:使用 set 避免重複計算同一島嶼(一個 0 格四鄰可能有多個格子屬於同一島嶼)。
C++ 解法
複雜度分析
時間複雜度:O(n² · α(n²)) ≈ O(n²) — 第一階段遍歷所有格子並進行 union 操作;第二階段對每個 0 格查四鄰(最多 4 次 find),整體接近 O(n²)。
空間複雜度:O(n²) — parent 和 area 各長 n²;第二階段的 unordered_set 每次最多 4 個元素,O(1) 額外空間。
虛擬碼
1. Initialize Union-Find arrays: parent[i]=i, area[i]=0 for i in [0, n*n)
2. Phase 1 - Build islands:
For each cell (r, c) with grid[r][c] == 1:
Set area[r*n+c] = 1
If cell above is land: unite(current, above)
If cell left is land: unite(current, left)
(area is accumulated at the root during union)
3. Compute initial max = max area[find(i)] over all i
4. Phase 2 - Try each 0 cell:
For each cell (r, c) with grid[r][c] == 0:
sum = 1
seen = empty set
For each valid land neighbor (nr, nc):
root = find(nr*n + nc)
If root not in seen: sum += area[root]; add root to seen
ans = max(ans, sum)
5. Return ans其他解法
DFS 染色 O(n²):不用 Union-Find,改用 DFS 為每個島嶼染色(賦予唯一 ID)並記錄面積,存入 map<id, area>。第二階段同樣枚舉 0 格。優點是 DFS 染色邏輯清晰;缺點是需要額外的 id 矩陣儲存每格的島嶼 ID,且 DFS 有遞迴深度的限制(n 最大 500,需注意 stack overflow)。
BFS 染色 O(n²):以 BFS 替代 DFS 進行島嶼染色,避免遞迴 stack overflow 問題,適合超大網格。優點是安全、迭代;缺點是需要額外的佇列空間,常數略大於 DFS。
暴力枚舉 O(n⁴):對每個 0 格翻轉後重新 BFS/DFS 計算最大島嶼。優點是完全不需要預處理;缺點是時間複雜度極高(n=500 時約 6.25×10¹⁰ 次操作),完全無法通過本題,僅適合驗證小樣本的正確性。
延伸思考
- 若允許翻轉最多 k 個
0為1(而非僅 1 個),答案如何求?此時問題複雜度如何變化? - 若網格是三維的(
n × n × n立方體,六個方向相鄰),本演算法如何擴展?空間複雜度如何? - 本題若改成「最小化翻轉數以使所有陸地連通」,這是什麼類型的問題?與本題有何關聯?