题目:
给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
解答:
方法一:BFS
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
#BFS
m=len(grid)
n=len(grid[0])
directions=[[-1,0],[1,0],[0,-1],[0,1]]
q=deque()
#左右边界
for i in range(m):
if grid[i][0]==1:
q.append((i,0))
grid[i][0]=2
if grid[i][n-1]==1:
q.append((i,n-1))
grid[i][n-1]=2
#上下边界
for j in range(1,n-1):
if grid[0][j]==1:
q.append((0,j))
grid[0][j]=2
if grid[m-1][j]==1:
q.append((m-1,j))
grid[m-1][j]=2
def InArea(i,j):
if 0<=i<m and 0<=j<n:
return True
return False
#从边界上的陆地单元格出发,标记与其直接或间接相连的单元格
while q:
x,y=q.popleft()
for dx,dy in directions:
curx,cury=x+dx,y+dy
if InArea(curx,cury) and grid[curx][cury]==1:
q.append((curx,cury))
grid[curx][cury]=2
res=0
for i in range(1,m-1):
for j in range(1,n-1):
if grid[i][j]==1:
res+=1
return res
方法二:DFS
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
#DFS
m=len(grid)
n=len(grid[0])
directions=[[-1,0],[1,0],[0,-1],[0,1]]
def InArea(i,j):
if 0<=i<m and 0<=j<n:
return True
return False
def dfs(i,j):
if not InArea(i,j) or grid[i][j]!=1:
return
#将其标记为已访问
grid[i][j]=2
for dx,dy in directions:
dfs(i+dx,j+dy)
#左右边界
for i in range(m):
dfs(i,0)
dfs(i,n-1)
#上下边界
for j in range(1,n-1):
dfs(0,j)
dfs(m-1,j)
res=0
for i in range(1,m-1):
for j in range(1,n-1):
if grid[i][j]==1:
res+=1
return res