太平洋大西洋水流

def pacific_atlantic_opt(heights):
    ROWS, COLS = len(heights), len(heights[0])
    pac, atl = set(), set()
    def dfs(r, c, visit, prevHeight):
        if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or heights[r][c] < prevHeight):
            return
        visit.add((r, c))
        dfs(r + 1, c, visit, heights[r][c])
        dfs(r - 1, c, visit, heights[r][c])
        dfs(r, c + 1, visit, heights[r][c])
        dfs(r, c - 1, visit, heights[r][c])
    for c in range(COLS):
        dfs(0, c, pac, heights[0][c])
        dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
    for r in range(ROWS):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, COLS - 1, atl, heights[r][COLS - 1])
    res = []
    for r in range(ROWS):
        for c in range(COLS):
            if (r, c) in pac and (r, c) in atl:
                res.append([r, c])
    return res

def pacific_atlantic_brute(heights):
    res = []
    ROWS, COLS = len(heights), len(heights[0])
    def can_reach(r, c, target_set):
        visited = set()
        q = [(r, c)]
        visited.add((r, c))
        while q:
            curr_r, curr_c = q.pop(0)
            if (curr_r, curr_c) in target_set: return True
            for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
                nr, nc = curr_r + dr, curr_c + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and (nr, nc) not in visited and heights[nr][nc] <= heights[curr_r][curr_c]:
                    visited.add((nr, nc))
                    q.append((nr, nc))
        return False
    pac_border = set([(0, c) for c in range(COLS)] + [(r, 0) for r in range(ROWS)])
    atl_border = set([(ROWS-1, c) for c in range(COLS)] + [(r, COLS-1) for r in range(ROWS)])
    for r in range(ROWS):
        for c in range(COLS):
            if can_reach(r, c, pac_border) and can_reach(r, c, atl_border):
                res.append([r, c])
    return res