1020.Number of Enclaves

tags: Medium,Array,DFS,BFS,Matrix

1020. 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% 像
Ron Chen 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的數量。
Yen-Chi ChenFri, 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;
}

寫得非常之笨
MarsgoatApr 8, 2023

Reference

回到題目列表