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立方體，六個方向相鄰），本演算法如何擴展？空間複雜度如何？ - 本題若改成「最小化翻轉數以使所有陸地連通」，這是什麼類型的問題？與本題有何關聯？