leetcode 周赛 162 5257. 统计封闭岛屿的数目 python

目录

1. 解答

有一个二维矩阵 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

提示：

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

解答

写了一个深搜，用于标记所有连通的陆地，首先用这个深搜把所有与边界相邻的陆地标记了。

然后遍历全图，看没有标记的陆地就调深搜标记并加一。

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        flag = [[True for i in range(m)] for i in range(n)]
        def dfs(i, j):
            flag[i][j] = False
            if j+1< m and grid[i][j+1] == 0 and flag[i][j+1]:
                dfs(i, j+1)
            if i+1< n and grid[i+1][j] == 0 and flag[i+1][j]:
                dfs(i+1, j)
            if j-1 > 0 and grid[i][j-1] == 0 and flag[i][j-1]:
                dfs(i, j-1)
            if i-1 > 0 and grid[i-1][j] == 0 and flag[i-1][j]:
                dfs(i-1, j)
        
        for i in range(n): 
            if grid[i][0] == 0 and flag[i][0] == True:
                dfs(i, 0)
            if grid[i][m-1] == 0 and flag[i][m-1] == True:
                dfs(i, m-1)

        for i in range(m): 
            if grid[0][i] == 0 and flag[0][i] == True:
                dfs(0, i)
            if grid[n-1][i] == 0 and flag[n-1][i] == True:
                dfs(n-1, i)
        cnt = 0
        for i in range(n):
            for j in range(m):
                if flag[i][j] == True and grid[i][j] == 0:
                    dfs(i, j)
                    cnt += 1
        return cnt