Leetcode 827:最大人工岛(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 827:最大人工岛(超详细的解法!!!)

in leetcode with 0 comment

在二维地图上,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。

说明:

解题思路

这个问题的思路非常简单,首先通过dfs找到所有的岛屿,并且将每个岛屿的大小记录。然后遍历所有海洋的位置,判断其四周是不是有岛屿,如果有的话,将所有岛屿的面积加起来记录其大小,最后通过所有值的最大值即可。

在寻找岛屿的过程中使用不同的颜色(数)将岛屿染色,这样方便我们后面判断哪些块是属于同一个岛屿。

class Solution:
    def largestIsland(self, grid):
        r, c = len(grid), len(grid[0])
        
        def check(x, y):
            if x < 0 or x >= r or y < 0 or y >= c:
                return 0
            return 1
        
        def dfs(x, y, color):
            if not check(x, y) or grid[x][y] != 1:
                return 0
            res = 1
            grid[x][y] = color
            for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                res += dfs(x + i, y + j, color)
            return res
        
        data, res, color = [0, 0], 0, 2
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 1:
                    data.append(dfs(i, j, color))
                    color += 1

        for i in range(r):
            for j in range(c):
                if grid[i][j] == 0:
                    colors = set(grid[x+i][y+j] for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]] if check(i + x, j + y))
                    res = max(res, sum(data[color] for color in colors) + 1)
        return r*c if res == 0 else res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses