题:
给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地(飞地)单元格的数量。
解:用2标记可以离开的陆地。
首先标记最外层的陆地2.然后从2出发,深度优先搜索周围的陆地都标记为2。
最后grid里没被标记的陆地就是飞地。
class Solution: def numEnclaves(self, grid: List[List[int]]) -> int: def dfs(i,j): nonlocal grid,m,n if i<0 or j<0 or i>=m or j >=n : return if grid[i][j]==1: grid[i][j] = 2 #可离开的陆地 dfs(i+1,j) dfs(i-1,j) dfs(i,j-1) dfs(i,j+1) return m, n = len(grid), len(grid[0]) cnt = 0 for i in range(m): grid[i][0] = 2 if grid[i][0] == 1 else 0 grid[i][n-1] = 2 if grid[i][n-1] == 1 else 0 for j in range(n): grid[0][j] = 2 if grid[0][j] == 1 else 0 grid[m-1][j] = 2 if grid[m-1][j] == 1 else 0 for i in range(m): for j in range(n): if grid[i][j] == 2: dfs(i+1,j) dfs(i-1,j) dfs(i,j-1) dfs(i,j+1) for i in range(m): for j in range(n): if grid[i][j] == 1: cnt += 1 return cnt