1254.统计封闭岛屿的数目.md

1254.统计封闭岛屿的数目

/*
 * @lc app=leetcode.cn id=1254 lang=typescript
 *
 * [1254] 统计封闭岛屿的数目
 */

// @lc code=start
function closedIsland(grid: number[][]): number {}
// @lc code=end

解法 1: 并查集

function closedIsland(grid: number[][]): number {
  const m = grid.length,
    n = grid[0].length
  const p = new Array(m * n).fill(-1)
  const flag = new Array(m * n).fill(0)
  const find = (i: number) => {
    if (p[i] < 0) return i
    p[i] = find(p[i])
    return p[i]
  }
  const union = (i: number, j: number) => {
    let ri = find(i),
      rj = find(j)
    if (ri === rj) return
    if (p[ri] > p[rj]) {
      ;[ri, rj] = [rj, ri]
    }
    p[ri] += p[rj]
    p[rj] = ri
    flag[ri] |= flag[rj]
  }
  const dirs = [
    [-1, 0],
    [0, -1],
    [1, 0],
    [0, 1],
  ]
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) continue
      const a = i * n + j
      for (const [di, dj] of dirs) {
        const ni = di + i,
          nj = dj + j
        if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
          flag[find(a)] = 1
        } else if (di + dj > 0 && !grid[ni][nj]) {
          union(a, ni * n + nj)
        }
      }
    }
  }
  let res = 0,
    vis: number[] = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) continue
      const a = i * n + j,
        r = find(a)
      if (vis[r]) continue
      vis[r] = 1
      if (!flag[r]) res++
    }
  }
  return res
}

Case

test.each([
  {
    input: {
      grid: [
        [0, 0, 1, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 1, 1, 1, 0],
      ],
    },
    output: 1,
  },
  {
    input: {
      grid: [
        [1, 1, 1, 1, 1, 1, 1, 0],
        [1, 0, 0, 0, 0, 1, 1, 0],
        [1, 0, 1, 0, 1, 1, 1, 0],
        [1, 0, 0, 0, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 0],
      ],
    },
    output: 2,
  },
  {
    input: {
      grid: [
        [1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1],
      ],
    },
    output: 2,
  },
])('input: grid = $input.grid', ({ input: { grid }, output }) => {
  expect(closedIsland(grid)).toEqual(output)
})