1
class Solution:
2
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
3
        # Purpose: find the cells that allow rain flow into the ocean
4
        # Method: DFS
5
        # Intuition: start from each border, check cell and neb, if OK, append to res
6

7
        # init: res, vis (pac, atl), ROW, COL
8
        res = []
9
        pac = set()
10
        atl = set()
11
        ROW = len(heights)
12
        COL = len(heights[0])
13

14
        # top and bottom row
15
        for col in range(COL):
16
            self.dfs(0, col, pac, heights[0][col], heights)
17
            self.dfs(ROW - 1, col, atl, heights[ROW - 1][col], heights)
18

19
        # left and right col
20
        for row in range(ROW):
21
            self.dfs(row, 0, pac, heights[row][0], heights)
22
            self.dfs(row, COL - 1, atl, heights[row][COL - 1], heights)
23

24
        # append to res
25
        for row in range(ROW):
26
            for col in range(COL):
27
                if (row, col) in pac and (row, col) in atl:
28
                    res.append([row, col])
29

30
        # return
31
        return res
32

33
    def dfs(self, row, col, vis, prev, heights):
34
        # hard-code definition
35
        try:
36
            cur = heights[row][col]
37
        except:
38
            pass
39

40
        # inbound, unvisited, increase from ocean
41
        if (
42
            (0 <= row < len(heights) and 0 <= col < len(heights[0]))
43
            and (cur >= prev)
44
            and ((row, col) not in vis)
45
        ):
46

47
            # add to visited
48
            vis.add((row, col))
49

50
            # check nebs
51
            self.dfs(row + 1, col, vis, cur, heights)
52
            self.dfs(row - 1, col, vis, cur, heights)
53
            self.dfs(row, col + 1, vis, cur, heights)
54
            self.dfs(row, col - 1, vis, cur, heights)