Leetcode[1020] number of enclaves python3 implementation (BFS, connected subtree search)

# Give you a size of m x n The binary matrix of grid , among 0 Represents an ocean cell 、1 Represents a land cell . 
# 
# once Move It refers to walking from one land cell to another （ On 、 Next 、 Left 、 Right ） Land cells or across grid The boundary of the . 
# 
# Return to grid unable The number of land cells that leave the grid boundary 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
# explain ： There are three 1 By 0 Surround . One 1 Not surrounded , Because it's on the border .
# 
# 
# Example 2： 
# 
# 
# Input ：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
# Output ：0
# explain ： all 1 Are on the boundary or can reach the boundary .
# 
# 
# 
# 
# Tips ： 
# 
# 
# m == grid.length 
# n == grid[i].length 
# 1 <= m, n <= 500 
# grid[i][j] The value of is 0 or 1 
# 
# Related Topics Depth-first search Breadth first search Union checking set Array matrix 123 0
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
ret = 0
m, n = len(grid), len(grid[0])
visited = [[False for _ in range(n)] for _ in range(m) ]
for i in range(m):
for j in range(n):
if grid[i][j]==1 and not visited[i][j]:
cnt = 0
dq = deque()
dq.append((i, j))
visited[i][j] = True
isEnclave = True
while dq:
cur_i, cur_j = dq.popleft()
cnt += 1
if cur_i==0 or cur_i==m-1 or cur_j==0 or cur_j==n-1:
isEnclave = False
for ni, nj in [(cur_i-1, cur_j), (cur_i+1, cur_j), (cur_i, cur_j-1), (cur_i, cur_j+1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]==1 and not visited[ni][nj]:
dq.append((ni, nj))
visited[ni][nj] = True
if isEnclave:
ret += cnt
return ret
# leetcode submit region end(Prohibit modification and deletion)