Description
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
Python3
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
def color(x, y):
if grid[x][y] == 0: return
grid[x][y] = 0
for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 <= dx < rows and 0 <= dy < cols:
color(dx, dy)
for i in range(rows):
color(i, 0)
color(i, cols - 1)
for j in range(cols):
color(0, j)
color(rows - 1, j)
res = 0
for i in range(1, rows):
for j in range(1, cols):
res += grid[i][j]
return res