0417：太平洋大西洋水流问题（★）

Ian

2016-02-21 约 434 字预计阅读 1 分钟次阅读

力扣第 417 题

题目

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [r_i, c_i] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[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]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10⁵

分析

从每个单元格开始遍历，显然会有很多重复路径
考虑反过来，从边界往里面遍历
多源 dfs/bfs 求出两边的列表，返回交集即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        def bfs(A):
            Q,vis = deque(A),set(A)
            while Q:
                i,j = Q.popleft()
                for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                    if 0<=x<m and 0<=y<n and H[x][y]>=H[i][j] and (x,y) not in vis:
                        vis.add((x,y))
                        Q.append((x,y))
            return vis
        H = heights
        m,n = len(H),len(H[0])
        A = [(0,j) for j in range(n)]+[(i,0) for i in range(1,m)] 
        B = [(m-1,j) for j in range(n)]+[(i,n-1) for i in range(m-1)]
        return [[i,j] for i,j in bfs(A)&bfs(B)]

67 ms

目录

0417：太平洋大西洋水流问题（★）

题目

分析

解答