Module gopy.dfs.pacific_atlantic
Expand source code
# Given an m x n matrix of non-negative integers representing
# the height of each unit cell in a continent,
# the "Pacific ocean" touches the left and top edges of the matrix
# and the "Atlantic ocean" touches the right and bottom edges.
# Water can only flow in four directions (up, down, left, or right)
# from a cell to another one with height equal or lower.
# Find the list of grid coordinates where water can flow to both the
# Pacific and Atlantic ocean.
# Note:
# The order of returned grid coordinates does not matter.
# Both m and n are less than 150.
# Example:
# 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 pacific_atlantic(matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
n = len(matrix)
if not n: return []
m = len(matrix[0])
if not m: return []
res = []
atlantic = [[False for _ in range (n)] for _ in range(m)]
pacific = [[False for _ in range (n)] for _ in range(m)]
for i in range(n):
dfs(pacific, matrix, float("-inf"), i, 0)
dfs(atlantic, matrix, float("-inf"), i, m-1)
for i in range(m):
dfs(pacific, matrix, float("-inf"), 0, i)
dfs(atlantic, matrix, float("-inf"), n-1, i)
for i in range(n):
for j in range(m):
if pacific[i][j] and atlantic[i][j]:
res.append([i, j])
return res
def dfs(grid, matrix, height, i, j):
if i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]):
return
if grid[i][j] or matrix[i][j] < height:
return
grid[i][j] = True
dfs(grid, matrix, matrix[i][j], i-1, j)
dfs(grid, matrix, matrix[i][j], i+1, j)
dfs(grid, matrix, matrix[i][j], i, j-1)
dfs(grid, matrix, matrix[i][j], i, j+1)
Functions
def dfs(grid, matrix, height, i, j)
-
Expand source code
def dfs(grid, matrix, height, i, j): if i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]): return if grid[i][j] or matrix[i][j] < height: return grid[i][j] = True dfs(grid, matrix, matrix[i][j], i-1, j) dfs(grid, matrix, matrix[i][j], i+1, j) dfs(grid, matrix, matrix[i][j], i, j-1) dfs(grid, matrix, matrix[i][j], i, j+1)
def pacific_atlantic(matrix)
-
:type matrix: List[List[int]] :rtype: List[List[int]]
Expand source code
def pacific_atlantic(matrix): """ :type matrix: List[List[int]] :rtype: List[List[int]] """ n = len(matrix) if not n: return [] m = len(matrix[0]) if not m: return [] res = [] atlantic = [[False for _ in range (n)] for _ in range(m)] pacific = [[False for _ in range (n)] for _ in range(m)] for i in range(n): dfs(pacific, matrix, float("-inf"), i, 0) dfs(atlantic, matrix, float("-inf"), i, m-1) for i in range(m): dfs(pacific, matrix, float("-inf"), 0, i) dfs(atlantic, matrix, float("-inf"), n-1, i) for i in range(n): for j in range(m): if pacific[i][j] and atlantic[i][j]: res.append([i, j]) return res