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

题目描述

827. 最大人工岛

在二维地图上， 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] 岛屿的最大面积的方法, 从这个点切入, 去寻找包含这个新陆地位置的最大岛屿面积即可.

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

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 遍历框架.

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