depth first search 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):
self.dfs(matrix, i, 0, p_visited, m, n)
self.dfs(matrix, i, n-1, a_visited, m, n)
for j in range(n):
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
#print 'visited',i,j
visited[i][j] = True
for dir in self.directions:
x, y = i + dir[0], j + dir[1]
#print 'trying to visit', x,y
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)
417. Pacific Atlantic Water Flow
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Given an m x n matrix of non-negative integers representi...
- Given an m x n matrix of non-negative integers representi...
- MediumGiven an m x n matrix of non-negative integers repr...
- G家的一道面试题，主要考搜索。方法是，由出口逆向进行搜索。分别找到属于Pacific和Atlantic的两个集合，...
- 看似平常的熟悉体验背后 很多女生可能很难理解男朋友玩游戏的时候完全不理睬自己的癫狂状态，不过如果说到学生时代越是感...
