统计封闭岛屿的数目

标签: 深度优先搜索 广度优先搜索 并查集 数组 矩阵

难度: Medium

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

示例 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

Submission

运行时间: 35 ms

内存: 16.6 MB

from typing import List


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        helper = [0, 0]  # 是否飞地, num

        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 1:
                return
            grid[i][j] = 1
            helper[1] += 1
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                helper[0] = 0  # 不是飞地
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    helper = [1, 0]  # 初始飞地
                    dfs(i, j)
                    res += helper[0]

        return res

Explain

此题解采用深度优先搜索（DFS）来遍历矩阵中的每个元素，寻找封闭岛屿。封闭岛屿定义为完全被1包围的0区域。解决方案中，首先通过遍历整个矩阵，每当遇到一个0，即尝试从该点出发进行DFS。在DFS过程中，首先标记当前节点为已访问（将其值置为1），然后检查其是否位于边界，若是，则当前岛屿不是封闭岛屿。DFS会递归地访问当前节点的上下左右节点。在DFS完成后，如果此岛屿是封闭的，则对结果计数器加一。通过这种方式，可以遍历整个矩阵，找出所有封闭岛屿并计数。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

from typing import List


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        helper = [0, 0]  # [是否封闭岛屿, 岛屿大小]

        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 1:
                return
            grid[i][j] = 1  # 标记访问过的土地
            helper[1] += 1  # 增加岛屿大小计数
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                helper[0] = 0  # 若节点在边界上, 则不是封闭岛屿
            dfs(i - 1, j)  # 向上移动
            dfs(i + 1, j)  # 向下移动
            dfs(i, j - 1)  # 向左移动
            dfs(i, j + 1)  # 向右移动

        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:  # 发现未访问的土地
                    helper = [1, 0]  # 初始化为封闭岛屿
                    dfs(i, j)
                    res += helper[0]  # 若为封闭岛屿, 增加计数

        return res

Explore

在DFS的实现中，每次调用函数前都检查当前坐标(i, j)是否越界，即是否满足0 <= i < m和0 <= j < n的条件。如果任一条件不满足，函数立即返回，不进行任何进一步的处理。这确保了DFS过程只在矩阵的有效范围内进行，从而防止了对矩阵外元素的访问。

在算法中，如果一个岛屿的任何部分触及到矩阵的边界，此岛屿就不能被认为是封闭的。这是因为边界外被默认为水域，所以如果岛屿触及边界，它实际上是与无限大的水域相连的，因此不是完全被水包围的封闭岛屿。虽然其它部分可能仍然被水包围，但整体而言，岛屿不满足封闭岛屿的定义。

在DFS过程中，一旦访问一个节点，我立即将其标记为已访问，即将该节点的值设为1。这种标记确保每个节点在整个DFS过程中只被访问一次，防止了无限递归的发生。因此，每次递归调用前都会检查当前节点是否已被标记为1，如果是，则直接返回，不再进行进一步的DFS。

在这个特定的问题（统计封闭岛屿的数目）中，岛屿的大小并不直接影响问题的解决，因为我们只需要知道岛屿是否封闭。岛屿大小的计数更多地用于可能的辅助分析，例如，分析岛屿的分布或大小范围。在其他上下文中，例如需要找出最大的封闭岛屿，岛屿大小的计数则会直接帮助解决问题。