Leetcode 1254:统计封闭岛屿的数目(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1254:统计封闭岛屿的数目(超详细的解法!!!)

in leetcode with 0 comment

有一个二维矩阵 grid ,每个位置要么是陆地(记号为 0 )要么是水域(记号为 1 )。

我们从一块陆地出发,每次可以往上下左右 4 个方向相邻区域走,能走到的所有陆地区域,我们将其称为一座「岛屿」。

如果一座岛屿 完全 由水域包围,即陆地边缘上下左右所有相邻区域都是水域,那么我们将其称为 「封闭岛屿」。

请返回封闭岛屿的数目。

示例 1:

输入:grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出:2
解释:
灰色区域的岛屿是封闭岛屿,因为这座岛屿完全被水域包围(即被 1 区域包围)。

示例 2:

输入:grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出:1

示例 3:

输入:grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出:2

提示:

解题思路

首先可以将所有的岛屿染成不同的颜色,然后剔除边缘岛屿的数量即可。

class Solution:
    def closedIsland(self, g: List[List[int]]) -> int:
        d = [0, 1, 0, -1, 0]
        r, c, res = len(g), len(g[0]), 2
              
        def dfs(x, y):
            for i in range(4):
                nx, ny = x + d[i], y + d[i + 1]
                if 0 <= nx < r and 0 <= ny < c and g[nx][ny] == 0:
                    g[nx][ny] = res
                    dfs(nx, ny)

        for i in range(r):
            for j in range(c):
                if g[i][j] == 0:
                    g[i][j] = res
                    dfs(i, j)
                    res += 1
        
        color = set([0, 1])
        for i in range(r):
            for j in range(c):
                if i == 0 or i == r - 1:
                    color.add(g[i][j])
                elif j == 0 or j == c - 1:
                    color.add(g[i][j])
        return res - len(color)

还有一种思路和这种做法类似,就是先将边缘的岛屿填充为1,然后再判断此时有多少个岛屿即可。

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

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

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

coordinate

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

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

Responses