--- title: "827. Making A Large Island" url: "https://laigary.com/interview/coding/827-making-a-large-island" type: "note" section: "coding" date: "2026-08-09" updated: "2026-08-09" tags: ["Breadth-First Search", "Depth-First Search"] --- # 827. Making A Large Island [827\. Making A Large Island](https://leetcode.com/problems/making-a-large-island/) 一張 `n x n` 的 0/1 方格，1 是陸地、0 是水，四方向相連的陸地算同一個島。**最多可以把一格 0 變成 1**（也可以不變），問這樣能得到的最大島嶼面積。 ## 思路 ### 要翻的那一格，只可能是貼著島的 0 第一個決定是：候選有哪些？直覺上是「所有的 0 都要試」，但其實只需要試**四周至少貼著一塊陸地的 0**。 這件事可以說得更死一點：只要格子裡同時存在 1 和 0，那就一定存在一個貼著島的 0 —— 從任何一個 0 走到任何一個 1，路上**第一次踩到 1 的前一格**，就是一個貼著島的 0。所以最佳解一定落在這個候選集合裡，不會漏。 ### 但「貼得多」不等於「變得大」 這是我一開始的直覺陷阱：以為連到越多島越好。其實不是，要看的是那些島**各自多大**： ```text 貼到 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 \le 500$，這個數量級跑不完。 ### 慢在哪裡 跟 [207](/interview/coding/207-course-schedule) 的暴力解是同一種浪費：**同一件事被重算了很多次。** 翻一格 0 並不會改變任何一個島的形狀，它只是把原本各自獨立的幾個島**接起來**。可是暴力解每翻一次就從零開始重量每一個島，那些面積根本沒變。 **所以島的面積應該先算好，之後查表。** ### 光記面積不夠，要記身分 第一個想法是「把每一格陸地改成它所屬島嶼的面積」，但這樣會壞掉，因為**面積會撞號**：兩個不同的島可以一樣大，這時候就分不出「兩邊是同一個島」還是「兩個剛好一樣大的島」。 ```text 1 0 1 1 0 1 1 1 1 ``` 這張圖其實只有一個島（左右兩條從底下連通），面積 7。翻 `(0,1)` 那格 0： ```text 它的鄰居 (0,0) 和 (0,2) 都是陸地，而且屬於同一個島 正確答案 = 1 + 7 = 8 只記面積、直接相加 = 1 + 7 + 7 = 15 ← 同一個島被加了兩次 ``` **面積只能拿來加總，不能拿來判斷「是不是同一個」。** 所以要記的是**編號**，再另外開一張「編號 → 面積」的表。有了編號，四個方向查出來的結果才能先去重、再查面積相加。 ### 編號蓋在原地，順便取代了 visited 編號可以直接蓋回 `grid` 裡，不用另外開一個矩陣。而且蓋編號這個動作**同時做完了兩件事**：記下這一格屬於誰，以及標記這一格走過了。 因為判斷「這格是還沒處理的陸地嗎」問的是「值等於 1 嗎」，只要編號不會等於 1，蓋過的格子自然就不會被再走一次： - 外層迴圈掃到已標記的格子 → 不等於 1 → 跳過 - flood fill 走到已標記的格子 → 不等於 1 → 停下來 所以不需要另外的 `visited`。這跟 [207 的 `state`](/interview/coding/207-course-schedule) 是同一招：一個標記同時承擔「走過了」和「身分是什麼」。 **代價是編號絕對不能跟 `0`／`1` 撞號**，這不是美觀問題而是正確性問題。編號從 `2` 開始就安全了；如果編號從 `1` 開始，第一個島會被蓋成 `1`，跟「還沒標記的陸地」完全分不出來，flood fill 會把自己剛蓋好的格子當成沒走過的陸地一直重走，停不下來。 ### 兩個邊界 - **整張圖都是 1** —— 一格 0 都掃不到，但這時候面積表裡只有一個島，值就是 $n^2$，答案直接從表裡取最大的就有了 - **整張圖都是 0** —— 面積表是空的，翻任何一格都只有它自己，答案是 1 ### 整理成流程 ```text 第一遍 BFS 每碰到一塊還沒標記的陸地 → 給一個新編號 一邊走一邊蓋編號、一邊數面積 → 記進面積表 第二遍 掃每一格 0 看四個方向，收集碰到的編號，去重 1 + 這些編號的面積總和 → 更新答案 答案 上面兩遍取最大（沒有 0 可翻時，就是面積表裡的最大值） ``` ## 解題方向 ```python 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` 本身，沒有另外開矩陣，也沒有用到遞迴。