dfs或者bfs
class Solution: def dfs(self, A, rows, cols, i, j): if not (0 <= i < rows and 0 <= j < cols): return elif A[i][j] == 0: return else: A[i][j] = 0 self.dfs(A, rows, cols, i + 1, j) self.dfs(A, rows, cols, i - 1, j) self.dfs(A, rows, cols, i, j + 1) self.dfs(A, rows, cols, i, j - 1) def numEnclaves(self, A: List[List[int]]) -> int: rows = len(A) cols = len(A[0]) for j in range(0, cols): if A[0][j] == 1: self.dfs(A, rows, cols, 0, j) if A[rows - 1][j] == 1: self.dfs(A, rows, cols, rows - 1, j) for i in range(0, rows): if A[i][0] == 1: self.dfs(A, rows, cols, i, 0) if A[i][cols - 1] == 1: self.dfs(A, rows, cols, i, cols - 1) ans = 0 for row in A: for a in row: if a == 1: ans += 1 return ans
或者
import queueclass Solution: def bfs(self, A, rows, cols, i, j): q = queue.Queue() A[i][j] = 0 q.put((i, j)) while not q.empty(): p = q.get() if 0 <= p[0] + 1 < rows and A[p[0] + 1][p[1]] == 1: A[p[0] + 1][p[1]] = 0 q.put((p[0] + 1, p[1])) if 0 <= p[0] - 1 < rows and A[p[0] - 1][p[1]] == 1: A[p[0] - 1][p[1]] = 0 q.put((p[0] - 1, p[1])) if 0 <= p[1] + 1 < cols and A[p[0]][p[1] + 1] == 1: A[p[0]][p[1] + 1] = 0 q.put((p[0], p[1] + 1)) if 0 <= p[1] - 1 < cols and A[p[0]][p[1] - 1] == 1: A[p[0]][p[1] - 1] = 0 q.put((p[0], p[1] - 1)) def numEnclaves(self, A: List[List[int]]) -> int: rows = len(A) cols = len(A[0]) for j in range(0, cols): if A[0][j] == 1: self.bfs(A, rows, cols, 0, j) if A[rows - 1][j] == 1: self.bfs(A, rows, cols, rows - 1, j) for i in range(0, rows): if A[i][0] == 1: self.bfs(A, rows, cols, i, 0) if A[i][cols - 1] == 1: self.bfs(A, rows, cols, i, cols - 1) ans = 0 for row in A: for a in row: if a == 1: ans += 1 return ans