1020. 飞地的数量【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

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

2. 🎯 s.1 - DFS

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[][]} grid
 * @return {number}
 */
var numEnclaves = function (grid) {
  const m = grid.length
  const n = grid[0].length
  const dfs = (i, j) => {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === 0) return
    grid[i][j] = 0
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j + 1)
    dfs(i, j - 1)
  }
  for (let i = 0; i < m; i++) {
    dfs(i, 0)
    dfs(i, n - 1)
  }
  for (let j = 0; j < n; j++) {
    dfs(0, j)
    dfs(m - 1, j)
  }
  let count = 0
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) count++
    }
  }
  return count
}

• 时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数
• 空间复杂度：$O(m\times n)$，递归调用栈的深度

算法思路：

• 从边界上的所有陆地单元格出发，用 DFS 将能到达边界的陆地全部标记为 0
• 遍历完边界后，统计矩阵中剩余的 1 的数量即为答案