数据结构算法（统计封闭岛屿的数目dfs）

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

2. 思路分析：

首先需要读懂题目，可以知道题目的关键词在于完全封闭，也就是陆地的周围都是水，所以靠近边缘的陆地是不属于这种情况的，所以我们应该使用dfs来将所有在边缘的陆地都变为水，这个技巧在水洼的数量的问题上也是同样适用的，变为水之后就可以解决重复访问的问题并且可以省略掉标记数组，我们通过dfs来将靠近边缘的陆地并且与之连接的陆地都变为水了，之后再调用dfs的方法，dfs调用多少次那么最终完全封闭的的陆地的数目就是多少了

3. 代码如下：

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # 左右上下四个方向
        pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        # 下面这个dfs方法是用来填充边缘的陆地为水
        def dfs(grid, current_r, current_c, r, c):
            for i in range(4):
                x, y = current_r + pos[i][0], current_c + pos[i][1]
                if 0 <= x < r and 0 <= y < c and grid[x][y] == 0:
                    grid[x][y] = 1
                    dfs(grid, x, y, r, c)

        # 这道题目与之前不同的是这里要求的是完全封闭的也就是陆地的四周都是水
        # 一个简单的想法是将靠近边缘的陆地都置为水
        r, c = len(grid), len(grid[0])
        for i in range(len(grid[0])):
            # 第一行与最后一行
            if grid[0][i] == 0:
                grid[0][i] = 1
                dfs(grid, 0, i, r, c)
            if grid[r - 1][i] == 0:
                grid[r - 1][i] = 1
                dfs(grid, r - 1, i, r, c)
        for i in range(len(grid)):
            # 第一列与最后一列
            if grid[i][0] == 0:
                grid[i][0] = 1
                dfs(grid, i, 0, r, c)
            if grid[i][c - 1] == 0:
                grid[i][c - 1] = 1
                dfs(grid, i, c - 1, r, c)

        res = 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 0:
                    dfs(grid, i, j, r, c)
                    res += 1
        return res

 

本文地址：https://blog.csdn.net/qq_39445165/article/details/107080214