【LeetCode】417-太平洋大西洋水流问题

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

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

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

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (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] <= 105

思路：

题目要求输出可以同时流向太平洋、大西洋的方格坐标，那么可以倒过来，从太平洋、大西洋边缘逆着推，得到可以流向太平洋的方格坐标和流向大西洋的方格坐标，两组数据相交即可得到可以同时流向太平洋大西洋的方格坐标

#深度优先遍历
class Solution(object):
    def pacificAtlantic(self, heights):
        m,n = len(heights),len(heights[0])#网格长宽

        def search(arr):#获得可以流向一个洋的所有方格坐标
            visited = set()#存储
            def dfs(x,y):
                if (x,y) in visited:
                    return
                visited.add((x,y))
                for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:#四个方向
                    if 0<=xx<m and 0<=yy<n and heights[xx][yy]>=heights[x][y]:#逆着推，所以下一块高度要大于等于
                        dfs(xx,yy)
            for x,y in arr:
                dfs(x,y)
            return visited   

        pacific = [(0,i) for i in range(n)]+[(i,0) for i in range(1,m)]
        atlantic = [(m-1,i) for i in range(n)]+[(i,n-1) for i in range(m-1)]
        return list(map(list,search(pacific)&search(atlantic)))

class Solution(object):
    def pacificAtlantic(self, heights):
        m,n = len(heights),len(heights[0])
        pacific = [(0,i) for i in range(n)]+[(i,0) for i in range(1,m)]
        atlantic = [(m-1,i) for i in range(n)]+[(i,n-1) for i in range(m-1)]
        visited1 = set()
        visited2 = set()

        while pacific:
            x,y = pacific[0]
            pacific.pop(0)
            if (x,y) not in visited1:
                visited1.add((x,y))
                for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                    if 0<=xx<m and 0<=yy<n and heights[xx][yy]>=heights[x][y]:
                        pacific.append((xx,yy))
        
        while atlantic:
            x,y = atlantic[0]
            atlantic.pop(0)
            if (x,y) not in visited2:
                visited2.add((x,y))
                for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                    if 0<=xx<m and 0<=yy<n and heights[xx][yy]>=heights[x][y]:
                        atlantic.append((xx,yy))
        return list(map(list,visited1&visited2))