【LeetCode】1020-飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

输入： grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出： 3
解释： 有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入： grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出： 0
解释： 所有 1 都在边界上或可以到达边界。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] 的值为 0 或 1

#广度优先遍历
class Solution(object):
    def numEnclaves(self, grid):
        m = len(grid)
        n = len(grid[0])
        
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    queue = []
                    queue.append((i,j))
                    grid[i][j]=0
                    cnt = 1#统计每一块岛屿的陆地数量
                    flag = 1#标志岛屿是否为有在边界的陆地
                    while queue:
                        x,y = queue[0]
                        queue.pop(0)
                        for xx,yy in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:
                            if not 0<=xx<m or not 0<=yy<n:
                                flag = 0#如果有陆地在边界，则这块岛屿的所有陆地都是是飞地
                            elif grid[xx][yy]==1:
                                queue.append((xx,yy))
                                grid[xx][yy]=0
                                cnt+=1
                    if flag:
                        result+=cnt
        return result              

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