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 either0
or1
.
SOLUTION:
class Solution:
def dfs(self, grid, i, j, m, n, visited):
visited.add((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] == 1 and (x, y) not in visited:
self.dfs(grid, x, y, m, n, visited)
def numEnclaves(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
boundary = set()
for i in range(m):
boundary.add((i, 0))
boundary.add((i, n - 1))
for i in range(n):
boundary.add((0, i))
boundary.add((m - 1, i))
globalvisited = set()
ctr = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
currvisited = set()
self.dfs(grid, i, j, m, n, currvisited)
if len(set.intersection(currvisited, boundary)) == 0:
ctr += len(currvisited)
return ctr
Top comments (0)