827. Making A Large Island

──────────────────────────────────────────────────────────────────────

一張 n x n 的 0/1 方格，1 是陸地、0 是水，四方向相連的陸地算同一個島。最多可以把一格 0 變成 1（也可以不變），問這樣能得到的最大島嶼面積。

思路

要翻的那一格，只可能是貼著島的 0

第一個決定是：候選有哪些？直覺上是「所有的 0 都要試」，但其實只需要試四周至少貼著一塊陸地的 0。

這件事可以說得更死一點：只要格子裡同時存在 1 和 0，那就一定存在一個貼著島的 0 —— 從任何一個 0 走到任何一個 1，路上第一次踩到 1 的前一格，就是一個貼著島的 0。所以最佳解一定落在這個候選集合裡，不會漏。

但「貼得多」不等於「變得大」

這是我一開始的直覺陷阱：以為連到越多島越好。其實不是，要看的是那些島各自多大：

貼到 2 個島，各 5 格   →  1 + 5 + 5 = 11
貼到 3 個島，各 1 格   →  1 + 1 + 1 + 1 = 4

連結數跟面積沒有關係。所以每一格候選要算的是「1 加上它周圍那些島的面積總和」，而不是數它碰到幾個島。

暴力法

順著上面直接做就是暴力法：對每一個候選的 0，把它翻成 1，然後整張圖重跑一次 BFS／DFS 量最大島，再翻回去換下一格。

面試時這就是要先講出來的第一版，但它會 TLE：候選最多 $n^{2}$ 格，每一格量一次要 $O (n^{2})$ ，合起來是 $O (n^{4})$ 。題目給到 $n \leq 500$ ，這個數量級跑不完。

慢在哪裡

跟 207 的暴力解是同一種浪費：同一件事被重算了很多次。

翻一格 0 並不會改變任何一個島的形狀，它只是把原本各自獨立的幾個島接起來。可是暴力解每翻一次就從零開始重量每一個島，那些面積根本沒變。

所以島的面積應該先算好，之後查表。

光記面積不夠，要記身分

第一個想法是「把每一格陸地改成它所屬島嶼的面積」，但這樣會壞掉，因為面積會撞號：兩個不同的島可以一樣大，這時候就分不出「兩邊是同一個島」還是「兩個剛好一樣大的島」。

1 0 1
1 0 1
1 1 1

這張圖其實只有一個島（左右兩條從底下連通），面積 7。翻 (0,1) 那格 0：

它的鄰居 (0,0) 和 (0,2) 都是陸地，而且屬於同一個島
正確答案            = 1 + 7      = 8
只記面積、直接相加   = 1 + 7 + 7 = 15   ← 同一個島被加了兩次

面積只能拿來加總，不能拿來判斷「是不是同一個」。 所以要記的是編號，再另外開一張「編號 → 面積」的表。有了編號，四個方向查出來的結果才能先去重、再查面積相加。

編號蓋在原地，順便取代了 visited

編號可以直接蓋回 grid 裡，不用另外開一個矩陣。而且蓋編號這個動作同時做完了兩件事：記下這一格屬於誰，以及標記這一格走過了。

因為判斷「這格是還沒處理的陸地嗎」問的是「值等於 1 嗎」，只要編號不會等於 1，蓋過的格子自然就不會被再走一次：

外層迴圈掃到已標記的格子 → 不等於 1 → 跳過
flood fill 走到已標記的格子 → 不等於 1 → 停下來

所以不需要另外的 visited。這跟 207 的 state 是同一招：一個標記同時承擔「走過了」和「身分是什麼」。

代價是編號絕對不能跟 0／1 撞號，這不是美觀問題而是正確性問題。編號從 2 開始就安全了；如果編號從 1 開始，第一個島會被蓋成 1，跟「還沒標記的陸地」完全分不出來，flood fill 會把自己剛蓋好的格子當成沒走過的陸地一直重走，停不下來。

兩個邊界

整張圖都是 1 —— 一格 0 都掃不到，但這時候面積表裡只有一個島，值就是 $n^{2}$ ，答案直接從表裡取最大的就有了
整張圖都是 0 —— 面積表是空的，翻任何一格都只有它自己，答案是 1

整理成流程

第一遍  BFS
        每碰到一塊還沒標記的陸地 → 給一個新編號
        一邊走一邊蓋編號、一邊數面積 → 記進面積表

第二遍  掃每一格 0
        看四個方向，收集碰到的編號，去重
        1 + 這些編號的面積總和 → 更新答案

答案    上面兩遍取最大（沒有 0 可翻時，就是面積表裡的最大值）

解題方向

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        area = {}      # 島的編號 → 面積
        island_id = 1  # 編號從 2 開始，才不會跟 0 / 1 撞號

        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        for i in range(n):
            for j in range(n):
                if grid[i][j] != 1:          # 還沒處理的陸地
                    continue
                island_id += 1
                grid[i][j] = island_id       # 起點也要蓋，面積從 1 起算
                q = deque([(i, j)])
                size = 1
                while q:
                    x, y = q.popleft()
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                            grid[nx][ny] = island_id   # 入隊時就蓋
                            q.append((nx, ny))
                            size += 1
                area[island_id] = size

        best = max(area.values(), default=1)

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    neighbors = set()
                    for dx, dy in directions:
                        nx, ny = i + dx, j + dy
                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] != 0:
                            neighbors.add(grid[nx][ny])
                    best = max(best, 1 + sum(area[label] for label in neighbors))

        return best

BFS 一定要「入隊時標記」

grid[nx][ny] = island_id 寫在 q.append(...) 的前面，這在 BFS 是必須的，不是風格問題。

如果等到 popleft() 之後才蓋編號，一格陸地會在它被彈出之前，被上下左右好幾個鄰居重複丟進 queue，面積就會多算，queue 也會膨脹。

DFS 用 stack 的話可以在彈出後才檢查（重複的那幾份會在 != 1 那關被擋掉），但 BFS 這樣寫就會出事 —— 這是兩者少數行為真的不一樣的地方。

其他兩行

best = max(area.values(), default=1) 一行處理掉了兩個邊界：整張圖都是 1 的時候，第二個迴圈一格 0 都掃不到，答案就是這裡取到的 $n^{2}$ ；整張圖都是 0 的時候 area 是空的，default=1 給出翻一格只有它自己的那個 1。

neighbors 用 set 就是在做去重 —— 上下左右可能有兩個方向落在同一個島上，那個島的面積只能算一次。

補充

area 一開始寫成 defaultdict(int)，結果把 bug 藏起來了。 那時候我漏掉了「蓋編號」那幾行，第二遍查到的編號其實是還沒被蓋過的 1；defaultdict 讓 area[1] 安靜地回傳 0，所以 [[1,0],[0,1]] 回傳 1（正確答案是 3），而且沒有任何錯誤訊息。

改成普通的 {} 之後，同樣的狀況會直接 KeyError: 1，一眼就指到問題。area 是一張「key 一定要存在」的表，defaultdict 只會幫忙把 bug 蓋掉。

defaultdict 適合的是不在乎 key 存不存在的表 —— 像這題的鄰接表，查一個沒有鄰居的節點本來就該回空清單。只要 key 的有無本身帶著資訊，就要用普通的 dict。

複雜度

時間 $O (n^{2})$ — 第一遍每一格最多被蓋一次編號（蓋完就不再等於 1，也就不會再入隊），第二遍每一格看四個方向
空間 $O (n^{2})$ — 面積表最多裝 $O (n^{2})$ 個島；BFS 的 queue 最壞情況也會裝下整張圖

其中 $n$ 是格子的邊長，格子總數是 $n^{2}$ 。編號是蓋回 grid 本身，沒有另外開矩陣，也沒有用到遞迴。