1254.Number of Closed Islands
===

###### tags: `Medium`,`Array`,`DFS`,`BFS`,`Matrix`

[1254. Number of Closed Islands](https://leetcode.com/problems/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

> [name=Ron Chen][time=Thr, 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 };
}

> 想說跟圍棋數氣差不多意思，也用同個方法寫
> [name=Marsgoat][time=Thr, 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;
  }
}

> 前面的版本有點傻，根本不需要計算相連的水的數量，這樣改快了不少。
> [name=Marsgoat][time=Thr, Apr 6, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)