1254.Number of Closed Islands

tags: Medium,Array,DFS,BFS,Matrix

1254. Number of Closed Islands

題目描述

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

範例

Example 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
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Example 3:

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

Constraints:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

解答

python

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(x, y):
            if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
                grid[x][y] = 1
                dfs(x-1, y)
                dfs(x+1, y)
                dfs(x, y-1)
                dfs(x, y+1)

        for x in range(m):
            for y in range(n):
                if (x in (0, m - 1) or y in (0, n - 1)) and grid[x][y] == 0:
                    dfs(x, y)

        res = 0
        for x in range(m):
            for y in range(n):
                if grid[x][y] == 0:
                    dfs(x, y)
                    res += 1

        return res

Ron ChenThr, Apr 6, 2023

Javascript

function closedIsland(grid) {
  let result = 0;
  const n = grid.length;
  const m = grid[0].length;

  const visited = new Array(n).fill(false).map(() => new Array(m).fill(false));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (grid[i][j] === 0) {
        if (visited[i][j]) continue;
        const { water, isClosed } = getWater(grid, [i, j]);
        if (isClosed) result++;

        for (const w of water) {
          visited[w[0]][w[1]] = true;
        }
      }
    }
  }

  return result;
}

function getWater(grid, point) {
  const n = grid.length;
  const m = grid[0].length;
  const isInBounds = (x, y) => x < n && x >= 0 && y < m && y >= 0;
  const isEdge = (x, y) => x === n - 1 || x === 0 || y === 0 || y === m - 1;
  const visited = new Array(n).fill(false).map(() => new Array(m).fill(false));
  const water = [point];
  const stack = [point];
  visited[point[0]][point[1]] = true;
  let isClosed = true;

  while (stack.length) {
    const [x, y] = stack.pop();
    if (isEdge(x, y)) isClosed = false;
    const neighbors = [
      [x, y - 1],
      [x, y + 1],
      [x - 1, y],
      [x + 1, y],
    ];

    for (const neighbor of neighbors) {
      const [nx, ny] = neighbor;
      if (isInBounds(nx, ny) && !visited[nx][ny]) {
        if (grid[nx][ny] === 0) {
          stack.push(neighbor);
          water.push(neighbor);
          visited[nx][ny] = true;
        }
      }
    }
  }

  return { water, isClosed };
}

想說跟圍棋數氣差不多意思，也用同個方法寫
MarsgoatThr, Apr 6, 2023

function closedIsland2(grid) {
  let result = 0;
  const n = grid.length;
  const m = grid[0].length;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (grid[i][j] === 0) {
        if (isClosed([i, j])) result++;
      }
    }
  }

  return result;

  function isClosed(point) {
    const isInBounds = (x, y) => x < n && x >= 0 && y < m && y >= 0;
    const isEdge = (x, y) => x === n - 1 || x === 0 || y === 0 || y === m - 1;
    const stack = [point];
    let isClosed = true;

    while (stack.length) {
      const [x, y] = stack.pop();
      if (isEdge(x, y)) isClosed = false;
      grid[x][y] = 1;
      const neighbors = [
        [x, y - 1],
        [x, y + 1],
        [x - 1, y],
        [x + 1, y],
      ];

      for (const neighbor of neighbors) {
        const [nx, ny] = neighbor;
        if (isInBounds(nx, ny)) {
          if (grid[nx][ny] === 0) {
            stack.push(neighbor);
          }
        }
      }
    }

    return isClosed;
  }
}

前面的版本有點傻，根本不需要計算相連的水的數量，這樣改快了不少。
MarsgoatThr, Apr 6, 2023

Reference

回到題目列表