[leetcode] 417 - Pacific Atlantic current problem

There is one m × n Rectangular Island , And The Pacific Ocean and The Atlantic ocean adjacent . “ The Pacific Ocean ” On the left and upper boundary of the continent , and “ The Atlantic ocean ” On the right and lower boundaries of the continent .

The island is divided into a grid of square cells . Given a m x n The integer matrix of heights , heights[r][c] Representation coordinates (r, c) Upper cell Height above sea level .

There is more rain on the island , If the height of adjacent cells Less than or equal to The height of the current cell , The rain can go straight north 、 south 、 In the east 、 West flow to adjacent cells . Water can flow into the ocean from any cell near the ocean .

Return grid coordinates result Of 2D list , among result[i] = [ri, ci] Indicates that rainwater flows from the cell (ri, ci) flow It can flow to the Pacific Ocean or the Atlantic Ocean .

Example 1：

Input : 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]]
Output : [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2：

Input : heights = [[2,1],[1,2]]
Output : [[0,0],[0,1],[1,0],[1,1]]

Tips ：

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

Ideas ：

The topic requires that the output can flow to the Pacific Ocean at the same time 、 The grid coordinates of the Atlantic , Then you can turn it upside down , From the Pacific 、 The edge of the Atlantic Ocean pushes against , Get the grid coordinates that can flow to the Pacific Ocean and the grid coordinates that can flow to the Atlantic Ocean , When the two sets of data intersect, we can get the grid coordinates that can flow to the Pacific Ocean and the Atlantic Ocean at the same time

# Depth-first traversal 
class Solution(object):
    def pacificAtlantic(self, heights):
        m,n = len(heights),len(heights[0])# Grid length and width 

        def search(arr):# Get all the grid coordinates that can flow to a ocean 
            visited = set()# Storage 
            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)]:# Four directions 
                    if 0<=xx<m and 0<=yy<n and heights[xx][yy]>=heights[x][y]:# Push against , So the height of the next piece should be greater than or equal to 
                        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))