目录

1. 题目描述

2. 解题分析

3. 代码实现

1. 题目描述​​​​​​​

给你一个大小为 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-enclaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

        这道题目与Leetcode1254. 统计封闭岛屿的数目(medium)本质上是相同的问题。只不过leetcode1254是统计封闭岛屿的个数，封闭岛屿就是本题说所的飞地，本题改为统计各封闭岛屿的总的面积。所以只需要在leetcode1254的代码的基础上做小幅度的修改即可。

3. 代码实现

from typing import List
from collections import deque

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        if len(grid)==0 or len(grid[0])==0:
            return 0
        
        R,C       = len(grid),len(grid[0])
        totalGridCnt = 0
        for r in range(1,len(grid)-1):
            for c in range(1,len(grid[0])-1):
                if grid[r][c] == 1:
                    isClosedIsland = True
                    gridCnt = 1
                    q = deque([(r,c)])
                    grid[r][c] = 0
                    while len(q)>0:
                        (r0,c0) = q.popleft()
                        for x,y in [(r0-1,c0),(r0+1,c0),(r0,c0-1),(r0,c0+1)]:
                            if 0<=x<R and 0<=y<C and grid[x][y]==1:
                                if x==0 or x==R-1 or y==0 or y==C-1: # Not closed island
                                    isClosedIsland = False
                                # Even not closed island, the search has to continue to flag the island.
                                q.append((x,y))
                                grid[x][y] = 0
                                gridCnt += 1
                    totalGridCnt = totalGridCnt + (gridCnt if isClosedIsland else 0)
        return totalGridCnt
                        
if __name__ == '__main__':
    sln = Solution()

    grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
    print(sln.numEnclaves(grid))
    
    grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
    print(sln.numEnclaves(grid))

        执行用时：224 ms, 在所有 Python3 提交中击败了17.98%的用户

        内存消耗：16 MB, 在所有 Python3 提交中击败了71.12%的用户

        感到有点诧异。。。因为是在leetcode1254的基础上修改的代码，按说其性能表现应该与leetcode1254相当啊？官解除了广度优先搜索和深度优先搜索以外，还给了个基于并查集的解法，难道大部分人在这个问题上都学乖了改用并查集了^-^，好吧看来要学习一下并查集的解法了。

        回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)