> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/airbnb2025/827.making-a-large-island.md).

# 827.Making A Large Island

You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.

Return *the size of the largest **island** in* `grid` *after applying this operation*.

An **island** is a 4-directionally connected group of `1`s.

 

**Example 1:**

<pre><code><strong>Input: grid = [[1,0],[0,1]]
</strong><strong>Output: 3
</strong><strong>Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: grid = [[1,1],[1,0]]
</strong><strong>Output: 4
</strong><strong>Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: grid = [[1,1],[1,1]]
</strong><strong>Output: 4
</strong><strong>Explanation: Can't change any 0 to 1, only one island with area = 4.
</strong></code></pre>

&#x20;

**Constraints:**

* `n == grid.length`
* `n == grid[i].length`
* `1 <= n <= 500`
* `grid[i][j]` is either `0` or `1`.

### 解题思路

这个问题可以分为两个主要步骤：

1. **识别并标记所有现有岛屿**：使用DFS或BFS遍历矩阵，找到所有岛屿，并为每个岛屿分配一个唯一标识符，同时记录每个岛屿的面积。
2. **寻找最佳填海位置**：对于每个 0，检查其四周的岛屿标识符，计算将这些岛屿连接起来后的总面积（注意去重），找出能形成最大岛屿的 0。

```
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n,m = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        # calculate all areas and set grid[x][y] with id(auto-increase, from 2)
        areaid = 2
        id2size = {}
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    curarea = 0
                    queue = [(i, j)]
                    grid[i][j] = areaid
                    while queue:
                        x, y = queue.pop()
                        curarea += 1
                        
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                                grid[nx][ny] = areaid
                                queue.append((nx, ny))

                    id2size[areaid] = curarea
                    areaid += 1
        if not id2size:
            return 1 if n > 0 else 0
        res = max(id2size.values())
        for i in range(n):
            for j in range(m):
                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 < m and grid[nx][ny] > 1:
                            neighbors.add(grid[nx][ny])
                    cursum = 1+ sum(id2size[areaid] for areaid in neighbors)
                    res = max(res, cursum)
        return res


```