> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/search/sao-ge/pacific-atlantic-water-flow.md).

# Pacific Atlantic Water Flow

<https://leetcode.com/problems/pacific-atlantic-water-flow/description/>

> Given an`m x n`matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
>
> Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
>
> Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

## Thoughts

这题和01matrix很像, 只是不再要求distance最短了. 可以看作有两种点, matrix内的和matrix外的. 问能否从matrix内流向matrix外, 正常思路是从matrix内部开始检查. 但这样要一个个点查, 结果也不好复用. 因此我们可以从matrix外往内逆流而上, 检查所有能被matrix外点访问到的点. 分别执行这样的过程两次, 对应Pacific和Altantic. 然后再检查两个集合的交集即能流向两种边界的点的集合.

## Code

```
class Solution {
    private Set<Integer> bfs(Queue<int[]> queue, int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Set<Integer> reached = new HashSet<>();
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                int height;
                if (pos[1] == -1 || pos[0] == -1 || pos[0] == m || pos[1] == n) {
                    height = 0;
                } else {
                    height = matrix[pos[0]][pos[1]];
                }

                for (int[] dir : dirs) {
                    int x = pos[0] + dir[0];
                    int y = pos[1] + dir[1];
                    int id = x * n + y;
                    if (reached.contains(id)) {
                        continue;
                    }
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (matrix[x][y] >= height) {
                            reached.add(id);
                            queue.add(new int[]{x, y});
                        }
                    }
                }
            }
        }
        return reached;
    }

    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        int m = matrix.length;
        if (m == 0) {
            return res;
        }
        int n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            queue.add(new int[]{i, -1});
        }
        for (int j = 0; j < n; j++) {
            queue.add(new int[]{-1, j});
        }
        Set<Integer> reachedByP = bfs(queue, matrix);
        queue.clear();
        for (int i = 0; i < m; i++) {
            queue.add(new int[]{i, n});
        }
        for (int j = 0; j < n; j++) {
            queue.add(new int[]{m, j});
        }
        Set<Integer> reachedByA = bfs(queue, matrix);


        for (Integer id : reachedByP) {
            if (reachedByA.contains(id)) {
                res.add(new int[]{id / n, id % n});
            }
        }

        return res;
    }
}
```

## Analysis

时空复杂度都是O(MN).