# Python DFS bests 85%. Tips for all DFS in matrix question.

• The DFS solution is straightforward. Starting from each point, and dfs its neighbor if the neighbor is equal or less than itself. And maintain two boolean matrix for two oceans, indicating an ocean can reach to that point or not. Finally go through all nodes again and see if it can be both reached by two oceans. The trick is if a node is already visited, no need to visited again. Otherwise it will reach the recursion limits.

This question is very similar to https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ And here are some common tips for this kind of question

1. init a directions var like `self.directions = [(1,0),(-1,0),(0,1),(0,-1)]` so that when you want to explore from a node, you can just do
``````for direction in self.directions:
x, y = i + direction[0], j + direction[1]
``````
1. this is a what I normally do for a dfs helper method for exploring a matrix
``````def dfs(self, i, j, matrix, visited, m, n):
if visited:
# return or return a value
for dir in self.directions:
x, y = i + direction[0], j + direction[1]
if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j] (or a condition you want to skip this round):
continue
# do something like
visited[i][j] = True
# explore the next level like
self.dfs(x, y, matrix, visited, m, n)
``````

Hope it helps

Solution

``````class Solution(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix: return []
self.directions = [(1,0),(-1,0),(0,1),(0,-1)]
m = len(matrix)
n = len(matrix[0])
p_visited = [[False for _ in range(n)] for _ in range(m)]

a_visited = [[False for _ in range(n)] for _ in range(m)]
result = []

for i in range(m):
# p_visited[i][0] = True
# a_visited[i][n-1] = True
self.dfs(matrix, i, 0, p_visited, m, n)
self.dfs(matrix, i, n-1, a_visited, m, n)
for j in range(n):
# p_visited[0][j] = True
# a_visited[m-1][j] = True
self.dfs(matrix, 0, j, p_visited, m, n)
self.dfs(matrix, m-1, j, a_visited, m, n)

for i in range(m):
for j in range(n):
if p_visited[i][j] and a_visited[i][j]:
result.append([i,j])
return result

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)
# 113 / 113 test cases passed.
# Runtime: 196 ms
``````

Solution for longest increasing path in matrix

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix: return 0
self.directions = [(1,0),(-1,0),(0,1),(0,-1)]
m = len(matrix)
n = len(matrix[0])
cache = [[-1 for _ in range(n)] for _ in range(m)]
res = 0
for i in range(m):
for j in range(n):
cur_len = self.dfs(i, j, matrix, cache, m, n)
res = max(res, cur_len)
return res

def dfs(self, i, j, matrix, cache, m, n):
if cache[i][j] != -1:
return cache[i][j]
res = 1
for direction in self.directions:
x, y = i + direction[0], j + direction[1]
if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j]:
continue
length = 1 + self.dfs(x, y, matrix, cache, m, n)
res = max(length, res)
cache[i][j] = res
return res
``````

``````class Solution(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix:
return matrix
self.searchPath = [[0,1],[0,-1],[1,0],[-1,0]]
m = len(matrix)
n = len(matrix[0])
res = [[0 for _ in range(n)] for _ in range(m)] #Mask = 01, Top-left(Pacific), Mask = 10, Bottom-right(Atlantic), res[i][j] = 11
ans = []
for i in range(m):
self.dfs(matrix, res, i,  0, 1)
self.dfs(matrix, res, i, n-1, 2)
for i in range(n):
self.dfs(matrix, res, 0, i, 1)
self.dfs(matrix, res, m-1, i, 2)
for i in range(m):
for j in range(n):
if res[i][j] == 3:
ans.append([i,j])
return ans

def dfs(self, matrix, res, i, j, mask):
for p in self.searchPath:
x = i + p[0]
y = j + p[1]
if x >= 0 and x < len(matrix) and y>=0 and y < len(matrix[0]) and res[x][y]&mask == 0 and matrix[i][j]<=matrix[x][y]:
``````

• Another python using complex number to avoid boundary checking:

``````moves = [1, -1, 1j, -1j]

def pacificAtlantic(self, matrix):
m, n = len(matrix), len(zip(*matrix))
def bfs(matrix):
maps = {x + y*1j: matrix[x][y] for x in xrange(m) for y in xrange(n)}
visited = {x for x in xrange(m)} | {y * 1j for y in xrange(n)}
layer = set(visited)
while layer:
layer = {pos+mov    for pos in layer
for mov in moves
if	pos+mov in maps          and
pos+mov not in visited   and
maps[pos+mov] >= maps[pos]}
visited |= layer
return visited
points = bfs(matrix) & {m-1+n*1j-1j-pos for pos in bfs([row[::-1] for row in matrix[::-1]])}
return [[p.real, p.imag] for p in points]``````

• How does it make logical sense that at (2,0) in the pacific_visit matrix we have 0? Isn't the pacific/atlantic visit matrixes showing a 1 where water can be pushed from and thus being touched? Wouldn't all the borders technically have a 1 since they are touching a body of water? Maybe I'm not understanding the question clearly and someone can clarify.

Here's the example that I run where I get that the point (2,0) is 0 in the pacific visited 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

• I like to use inner function for dfs because it has access to variable reference declared in the outer function, thus it can have less parameters

``````def pacificAtlantic(self, matrix):
if not matrix or not matrix[0]:
return []

h, w = len(matrix), len(matrix[0])
top = zip(repeat(0, w), range(w))
bottom = zip(repeat(h-1, w), range(w))
left = zip(range(h), repeat(0, h))
right = zip(range(h), repeat(w-1, h))
reach = [[0] * w for _ in range(h)]
res = []
visited = set()

def dfs(i, j):
if (i,j) in visited:
return

if reach[i][j] == 3:
res.append((i,j))

for ii, jj in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
if not 0<=ii<h or not 0<=jj<w:
continue
if matrix[ii][jj] >= matrix[i][j]:
reach[ii][jj] |= reach[i][j]
dfs(ii, jj)

for i, j in chain(top, left):
reach[i][j] |=1
dfs(i, j)

visited.clear()
for i, j in chain(right, bottom):
reach[i][j] |=2
dfs(i, j)

return res``````

• Nice solution. Thanks.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.