「每日LeetCode」2022年2月12日

本文最后更新于：2023年3月19日 晚上

  1. 飞地的数量

1020. 飞地的数量

image.png
给你一个大小为 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 没有被包围，因为它在边界上。
image.png
示例 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

思路

深度优先，遍历每一块地，如果到达了边界，将 flag 设为 false。如果遍历完所有地，始终没到边界，计数。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @param {number[][]} grid
 * @return {number}
 */
var numEnclaves = function (grid) {
  let res = 0,
    flag = true;

  const dfs = (i, j) => {
    if (!grid[i][j]) return 0;
    grid[i][j] = 0;
    if (
      i === 0 ||
      i === grid.length - 1 ||
      j === 0 ||
      j === grid[i].length - 1
    ) {
      flag = false;
    }

    const top = grid[i - 1] && grid[i - 1][j],
      bottom = grid[i + 1] && grid[i + 1][j],
      left = grid[i][j - 1],
      right = grid[i][j + 1];

    let res = 0;

    if (top) res += dfs(i - 1, j);
    if (bottom) res += dfs(i + 1, j);
    if (left) res += dfs(i, j - 1);
    if (right) res += dfs(i, j + 1);

    return res + 1;
  };

  for (let i = 1; i < grid.length; i++) {
    for (let j = 1; j < grid[i].length; j++) {
      if (!grid[i][j]) continue;
      flag = true;
      count = dfs(i, j);
      if (flag) res += count;
    }
  }

  return res;
};