【LeetCode】1254-统计封闭岛屿的数量

二维矩阵 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：

输入： g rid = [[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(object):
    def closedIsland(self, grid):
        n = len(grid)
        m = len(grid[0])
        landcount = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j]==0:
                    val = 1
                    grid[i][j]=1
                    queue=[]
                    queue.append((i,j))
                    while queue:
                        x,y = queue[0]
                        queue.pop(0)
                        for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                            if not 0<=xx<n or not 0<=yy<m:
                                val=0
                            elif grid[xx][yy]==0:
                                grid[xx][yy]=1
                                queue.append((xx,yy))
                    landcount+=val
        return landcount

#深度优先遍历
class Solution(object):
    def closedIsland(self, grid):
        n = len(grid)
        m = len(grid[0])
        landcount = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j]==0:
                    val = 1
                    grid[i][j]=1
                    stack=[]
                    stack.append((i,j))
                    while stack:
                        x,y = stack[-1]
                        stack.pop()
                        for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                            if not 0<=xx<n or not 0<=yy<m:
                                val=0
                            elif grid[xx][yy]==0:
                                grid[xx][yy]=1
                                stack.append((xx,yy))
                    landcount+=val
        return landcount