LeetCode-Python-1254. 统计封闭岛屿的数目（DFS）

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

思路：

问岛屿的一般都是DFS BFS UFS。

感觉这题是某道老题（老题大意是，判断有多少个岛屿不能和四边相邻）变种，题号记不清了，下次找出来再写在这里。

从四条边出发，把所有DFS能走到的0染色成-1，剩下的0就都是被1完整包围的0了。

然后再遍历整个grid，如果发现一个0，就把其用DFS能走到的所有相邻0都染色成-1（这样保证了同一个岛屿里的0不会被重复计算在答案里）， 然后答案 +=1。

时间复杂度：O（M * N）

空间复杂度：O（1）

class Solution(object):
    def closedIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        def dfs(x0, y0):
            if grid[x0][y0] == 0:
                grid[x0][y0] = -1
                for k in range(4):
                    x = x0 + dx[k]
                    y = y0 + dy[k]
                    
                    if 0 < x < m and 0 < y < n and grid[x][y] == 0:
                        dfs(x, y)
                        
        for j in range(n):
            dfs(0, j)
        for j in range(n):
            dfs(m - 1, j)
        for i in range(m):
            dfs(i, 0)
        for i in range(m):
            dfs(i, n - 1)
        
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    res += 1
                    dfs(i, j)
        return res