class Solution(object):
def __init__(self):
self.cons = 0
self.S = list() def dfs(self,m,n,v,A):
while len(self.S) > 0:
cur = self.S.pop(-1)
cur_x = cur[0]
cur_y = cur[1]
v[cur_x][cur_y] = 1
self.cons += 1 if cur_x > 0 and A[cur_x-1][cur_y]==1 and v[cur_x-1][cur_y] == 0:
self.S.append([cur_x-1,cur_y])
self.dfs(m,n,v,A) if cur_x < m - 1 and A[cur_x + 1][cur_y]==1 and v[cur_x + 1][cur_y]== 0:
self.S.append([cur_x+1,cur_y])
self.dfs(m,n,v,A) if cur_y > 0 and A[cur_x][cur_y-1]==1 and v[cur_x][cur_y-1]==0:
self.S.append([cur_x,cur_y-1])
self.dfs(m,n,v,A) if cur_y < n - 1 and A[cur_x][cur_y+1]==1 and v[cur_x][cur_y+1]==0:
self.S.append([cur_x,cur_y+1])
self.dfs(m,n,v,A) return 0 def numEnclaves(self, A: 'List[List[int]]') -> int:
row = len(A)
coloum = len(A[0])
visited = [[0 for c in range(coloum)] for r in range(row)]
sumsA = 0
for i in range(row):
for j in range(coloum):
sumsA += A[i][j]
if sumsA == 0:
return 0 #first row and last row
for i in [0,row-1]:
for j in range(coloum):
if A[i][j] == 0 or visited[i][j] == 1:
continue
else:
self.S.append([i,j])
self.dfs(row,coloum,visited,A) #first coloum and last coloum
for j in [0,coloum - 1]:
for i in range(row):
if A[i][j] == 0 or visited[i][j] == 1:
continue
else:
self.S.append([i,j])
self.dfs(row,coloum,visited,A) return sumsA - self.cons
解决思路是使用DFS，为了提高效率，只扫描外边框（第一行，最后一行，第一列，最后一列），并使用一个数组记录是否已经访问。