class Solution:
def __init__(self):
self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m = len(heights)
n = len(heights[0])
visited1 = [[False] * n for _ in range(m)]
for j in range(n):
if not visited1[0][j]:
self.dfs(heights, 0, j, visited1)
for i in range(m):
if not visited1[i][0]:
self.dfs(heights, i, 0, visited1)
visited2 = [[False] * n for _ in range(m)]
for j in range(n):
if not visited2[m-1][j]:
self.dfs(heights, m-1, j, visited2)
for i in range(m):
if not visited2[i][n-1]:
self.dfs(heights, i, n-1, visited2)
res = []
for i in range(m):
for j in range(n):
if visited1[i][j] and visited2[i][j]:
res.append([i, j])
return res
def dfs(self, heights, i, j, visited):
visited[i][j] = True
for dir in self.dirs:
new_i = i + dir[0]
new_j = j + dir[1]
if new_i < 0 or new_i >= len(heights) or new_j < 0 or new_j >= len(heights[0]):
continue
if not visited[new_i][new_j] and heights[new_i][new_j] >= heights[i][j]:
self.dfs(heights, new_i, new_j, visited)