Pacific Atlantic Water Flow

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.
Given the following 5x5 matrix:  Pacific ~   ~   ~   ~   ~ 
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
def pacificAtlantic(self, matrix):
if not matrix: return []
direction = [[-1,0], [0,1], [1,0], [0,-1]]
colLen = len(matrix)
rowLen = len(matrix[0])
canReachP = [[False for _ in range(rowLen)] for _ in range(colLen)]
canReachA = [[False for _ in range(rowLen)] for _ in range(colLen)]
ans = []
def dfs(canReach, x, y):
if canReach[x][y]:
return
canReach[x][y] = True
for each in direction:
row = x + each[0]
col = y + each[1]
if row >= 0 and row < colLen and col >= 0 and col < rowLen and matrix[x][y] <= matrix[row][col]:
dfs(canReach, row, col)
return
for i in range(rowLen):
dfs(canReachP, 0, i)
dfs(canReachA, colLen-1, i)
for j in range(colLen):
dfs(canReachP, j, 0)
dfs(canReachA, j, rowLen-1)
for n in range(colLen):
for m in range(rowLen):
if canReachP[n][m] and canReachA[n][m]:
ans.append([n,m])
return ans
class Solution(object):
def pacificAtlantic(self, matrix):
“””
:type matrix: List[List[int]]
:rtype: List[List[int]]
“””
if not matrix: return []
self.directions = [[-1,0], [0,1], [1,0], [0,-1]]
colLen = len(matrix)
rowLen = len(matrix[0])
canReachP = [[False for _ in range(rowLen)] for _ in range(colLen)]
canReachA = [[False for _ in range(rowLen)] for _ in range(colLen)]
ans = []

for j in range(colLen):
self.dfs(matrix, j, 0, canReachP, colLen, rowLen)
self.dfs(matrix, j, rowLen-1, canReachA, colLen, rowLen)

for i in range(rowLen):
self.dfs(matrix, 0, i, canReachP, colLen, rowLen)
self.dfs(matrix, colLen-1, i, canReachA, colLen, rowLen)


for n in range(colLen):
for m in range(rowLen):
if canReachP[n][m] and canReachA[n][m]:
ans.append([n,m])
return ans

def dfs(self, matrix, i, j, visited, m, n):
# when dfs called, meaning its caller already verified this point
visited[i][j] = True
for dir in self.directions:
x, y = i + dir[0], j + dir[1]
if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] < matrix[i][j]:
continue
self.dfs(matrix, x, y, visited, m, n)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store