1020.Number of Enclaves
===

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

[1020. Number of Enclaves](https://leetcode.com/problems/number-of-enclaves/)

### 題目描述

You are given an `m x n` binary matrix `grid`, where `0` represents a sea cell and `1` represents a land cell.

A **move** consists of walking from one land cell to another adjacent (**4-directionally**) land cell or walking off the boundary of the `grid`.

Return *the number of land cells in* `grid` *for which we cannot walk off the boundary of the grid in any number of **moves**.*

### 範例

**Example 1:**


Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

**Example 2:**


Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

**Constraints**:

* `m` == `grid.length`
* `n` == `grid[i].length`
* 1 <= `m`, `n` <= 500
* `grid[i][j]` is either `0` or `1`.

### 解答
#### Python

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

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

        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] == 1:
                    dfs(x, y, 0)

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

        return self.res

> 跟昨天那題解法 87% 像
> [name=Ron Chen][time= Fri, Apr 7, 2023]

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            grid[i][j] = 0
            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    dfs(x, y)
        
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0 or i == m-1 or j == n-1) and grid[i][j]:
                    dfs(i, j)
        
        return sum(sum(row) for row in grid)

> 從四個邊下去dfs，走過的地方都修改為0，最後回傳加總得到仍為1的數量。
> [name=Yen-Chi Chen][time=Fri, Apr 7, 2023]

#### Javascript

function numEnclaves(grid) {
  let result = 0;
  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;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (grid[i][j] === 1) {
        const { isEnclave, lands } = search([i, j]);
        if (isEnclave) {
          result += lands.length;
          for (const land of lands) {
            grid[land[0]][land[1]] = 0;
          }
        }
      }
    }
  }

  function search(land) {
    let isEnclave = true;
    const stack = [land];
    const lands = [land];
    grid[land[0]][land[1]] = 0;

    while (stack.length) {
      const [x, y] = stack.pop();
      if (isEdge(x, y)) isEnclave = 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) && grid[nx][ny] === 1) {
          stack.push(neighbor);
          lands.push(neighbor);
          grid[nx][ny] = 0;
        }
      }
    }

    return { isEnclave, lands };
  }

  return result;
}

> 寫得非常之笨
> [name=Marsgoat][time=Apr 8, 2023]
### Reference

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