# \[827]\[困难]\[DFS] 最大人工岛

## 题目描述

[827. 最大人工岛](https://leetcode-cn.com/problems/making-a-large-island/)

在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

示例 1:

```
输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
```

示例 2:

```
输入: [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
```

示例 3:

```
输入: [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
```

说明:

* 1 <= grid.length = grid\[0].length <= 50
* 0 <= grid\[i]\[j] <= 1

## 解题思路

### DFS

一种思路是, 遍历所有为`0`的位置, 将这个`0`置为`1`, 相当于将这块土地进行了填海. 之后按照[\[695\]\[中等\]\[DFS\] 岛屿的最大面积](/garnet/suan-fa/dfs/695-dao-yu-de-zui-da-mian-ji.md)的方法, 从这个点切入, 去寻找包含这个新陆地位置的最大岛屿面积即可.

这样做的时间复杂度为$$O(N^4)$$. 时间复杂度过高, 会导致超时.

```python
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])

        def dfs(i, j, count):
            if not 0 <= i < n or not 0 <= j < m:
                return count
            if grid[i][j] == 0 or grid[i][j] == 2:
                return count

            grid[i][j] = 2
            t = count + 1

            t = dfs(i - 1, j, t)
            t = dfs(i + 1, j, t)
            t = dfs(i, j - 1, t)
            t = dfs(i, j + 1, t)
            return t

        max_area = 0
        raw = copy.deepcopy(grid)
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0:
                    grid[i][j] = 1
                    cur_area = dfs(i, j, 0)
                    max_area = max(max_area, cur_area)
                    grid = copy.deepcopy(raw)
        return max_area if max_area else n * m
```

### DFS + 岛屿编号

对网格做了两遍 DFS：第一遍 DFS 遍历陆地格子，计算每个岛屿的面积并标记岛屿；第二遍 DFS 遍历海洋格子，观察每个海洋格子相邻的陆地格子。

详情参考[岛屿类问题的通用解法、DFS 遍历框架](https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/).

```python
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])

        def dfs(i, j, count, t_index):
            if not 0 <= i < n or not 0 <= j < m:
                return count
            if grid[i][j] == 0 or grid[i][j] == t_index:
                return count

            grid[i][j] = t_index
            t = count + 1

            t = dfs(i - 1, j, t, t_index)
            t = dfs(i + 1, j, t, t_index)
            t = dfs(i, j - 1, t, t_index)
            t = dfs(i, j + 1, t, t_index)
            return t

        index, mapping = 2, dict()
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    cur_area = dfs(i, j, 0, index)
                    mapping[index] = cur_area
                    index += 1

        max_area = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0:
                    cur_area, seen = 1, set()
                    for ti, tj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                        if 0 <= ti < n and 0 <= tj < m and grid[ti][tj] != 0 and grid[ti][tj] not in seen:
                            cur_area += mapping[grid[ti][tj]]
                            seen.add(grid[ti][tj])
                    max_area = max(max_area, cur_area)

        return max_area if max_area else n * m
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dfs/827-zui-da-ren-gong-dao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.