417. 太平洋大西洋水流问题(Medium)

题目描述

给定一个二维的非负整数矩阵，每个位置的值表示海拔高度。假设左边和上边是太平洋，右边和下边是大西洋，求从哪些位置向下流水，可以流到太平洋和大西洋。水只能从海拔高的位置 流到海拔低或相同的位置。

样例

Input:
给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * 大西洋

Output:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

题解

使用深度搜索解决：

• 主函数：沿着 太平洋 和 大西洋 沿岸加入搜索，当没有访问过就加入深搜
• 辅函数：递归遍历更高的土地

Python 示例

代码稍微有点多，所以可以用于平时练习

# 辅函数：递归遍历更高的土地
def dfs(matrix, can_reach, i, j):
    can_reach[i][j] = 1
    for d in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
        x = i + d[0]
        y = j + d[1]
        if 0 <= x < len(matrix) and \
           0 <= y < len(matrix[0]) and \
           not can_reach[x][y] and matrix[i][j] <= matrix[x][y]:
           dfs(matrix, can_reach, x, y)
        
class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        if not matrix: return []
        n, m = len(matrix), len(matrix[0])
        can_reach_atlantic = [[0] * m for _ in range(n)]
        can_reach_pacific = [[0] * m for _ in range(n)]
				
        # 主函数：沿着 `太平洋` 和 `大西洋` 沿岸加入搜索，当没有访问过就加入深搜
        for i in range(n):
            dfs(matrix, can_reach_pacific, i, 0)
            dfs(matrix, can_reach_atlantic, i, m - 1)
        
        for i in range(m):
            dfs(matrix, can_reach_pacific, 0 , i)
            dfs(matrix, can_reach_atlantic, n - 1, i)
        
        # 求出答案
        ans = []
        for i in range(n):
            for j in range(m):
                if can_reach_atlantic[i][j] and can_reach_pacific[i][j]:
                    ans.append([i, j])
        return ans