# 417. Pacific Atlantic Water Flow
#### Difficulty: Medium
link: https://leetcode.com/problems/pacific-atlantic-water-flow/

### 1. BFS
#### $O(mn)$ runtime, $O(mn)$ space
以太平洋和大西洋接觸的cells當作出發點，只要鄰居的cell高度更高就代表有邊，以BFS求得所有能流向兩邊海洋的cells，再彼此取交集。

##### python

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

        pacific_cells = bfs([(i, 0) for i in range(m)] + [(0, j) for j in range(n)])
        atlantic_cells = bfs([(i, n-1) for i in range(m)] + [(m-1, j) for j in range(n)])
        
        return [list(cell) for cell in pacific_cells & atlantic_cells]

###### tags: `leetcode`