难度: Medium
给你一个大小为 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.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] 的值为 0 或 1运行时间: 67 ms
内存: 27.7 MB
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])
def dfs(row, col):
# print(row,col)
grid[row][col] = 0
if row+1<nrow and grid[row+1][col]==1:
dfs(row+1,col)
if col+1<ncol and grid[row][col+1] == 1:
dfs(row, col+1)
if row-1>=0 and grid[row-1][col]==1:
dfs(row-1,col)
if col-1>=0 and grid[row][col-1]==1:
dfs(row, col-1)
for i in [0,nrow-1]:
for j in range(ncol):
if grid[i][j] == 1:
dfs(i,j)
for j in [0,ncol-1]:
for i in range(nrow):
if grid[i][j] == 1:
dfs(i,j)
# print(grid)
return sum([i for li in grid for i in li])
此题目的核心思路是利用深度优先搜索（DFS）从矩阵的边缘开始搜索所有与边缘相连的陆地单元格，并将其标记为海洋（即将1变为0）。这样，矩阵中剩余的1即为被完全包围的陆地，无法通过移动到达边界。具体步骤包括：1. 从矩阵的四个边缘开始，对于每个边缘上的陆地单元格，执行DFS并标记所有可达的陆地单元格。2. 对整个矩阵进行遍历，统计未被标记（即未被转换为0的单元格）的陆地单元格数量，这些即为无法到达边界的陆地单元格。
时间复杂度: O(m * n)
空间复杂度: O(m * n)
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])
def dfs(row, col):
# 将当前单元格从陆地标记为海洋
grid[row][col] = 0
# 向下探索
if row+1<nrow and grid[row+1][col]==1:
dfs(row+1,col)
# 向右探索
if col+1<ncol and grid[row][col+1] == 1:
dfs(row, col+1)
# 向上探索
if row-1>=0 and grid[row-1][col]==1:
dfs(row-1,col)
# 向左探索
if col-1>=0 and grid[row][col-1]==1:
dfs(row, col-1)
# 从上下边界开始DFS
for i in [0,nrow-1]:
for j in range(ncol):
if grid[i][j] == 1:
dfs(i,j)
# 从左右边界开始DFS
for j in [0,ncol-1]:
for i in range(nrow):
if grid[i][j] == 1:
dfs(i,j)
# 计算剩余的陆地单元格数
return sum([i for li in grid for i in li])
从边缘的陆地单元格开始DFS的主要目的是标记那些可以直接或间接到达边缘的陆地单元格。这些单元格不被视为飞地，因为它们不是完全被水包围的。从边缘单元格开始可以直接排除这些单元格，从而在后续的遍历中，只需要关注那些未被访问过的陆地单元格，这些就是真正的飞地。如果从任意位置开始，会更复杂地判断一个陆地单元格是否能够到达边缘，增加算法的复杂度和执行时间。
在DFS过程中，每当访问一个陆地单元格，我们会立即将其标记为海洋（即将1变为0）。这种标记方式确保了一旦一个单元格被访问和处理过，它的值就会改变，从而避免在后续的DFS探索中被再次访问和处理。这是一种有效的防止重复访问的技术，因为它利用了问题本身的条件——即只有值为1的单元格才代表陆地。
在DFS的实现中，每次递归调用前都会检查当前单元格位置是否有效，即是否在矩阵边界内，并且单元格的值是否为1（表示陆地）。如果单元格位置超出矩阵边界或者其值不为1（已经是海洋或原本就是海洋），则递归调用会停止。这样的检查确保了DFS只在矩阵的有效范围内进行，并且只对陆地单元格进行处理。
算法执行结束后，所有可以到达边界的陆地单元格都已经被标记为海洋（值从1变为0）。因此，矩阵中剩余的所有1都代表那些无法到达边界的陆地单元格，即飞地。直接统计剩余的1的数量就可以得到飞地的数量。这里考虑了所有边界条件，因为算法从所有可能的边缘陆地单元格出发，确保了所有能到达边界的路径都被探索过。