题目内容

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回 网格坐标 result 的 2D列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。

示例 1：

输入: 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]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示：

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

解题思路

对于相邻单元格，水可以从高的单元格流向低的单元格，水流分为两个方向，流向太平洋和流向大西洋，即向左和上流以及向右和下流，题目求的是同时能流向左上和右下的单元格的坐标集合。可以分开求能流向左上的单元格和能流向右下的单元格，两个集合求交集就是最终结果。
可以用BFS来做，流向右下的情况从左边界和上边界开始，向右下移动，记录符合条件的单元格坐标；流向左上的情况从右边界和下边界开始，向左上移动，记录符合条件的单元格坐标，最后对以上两个结果求交集就是最终答案。

public class Solution {

    int[][] grid;
    int w, h;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        if (heights == null) {
            return null;
        }
        grid = heights;
        w = heights.length;
        h = heights[0].length;
        // 创建两个boolean存放符合条件的单元格，t[m][n]=true表示这个单元格可以流向边界
        // t1是流向右下
        boolean[][] t1 = new boolean[w][h];
        // t2是流向左上
        boolean[][] t2 = new boolean[w][h];
        // 双端队列，用于bfs
        Deque<int[]> d1 = new LinkedList<>();
        Deque<int[]> d2 = new LinkedList<>();
        // 初始化两个队列，分别存左边界上边界的单元格坐标和右边界下边界的单元格坐标
        // 边界视为可以直接流向大洋，所以设置对应的boolean数组元素为true
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if (i == 0 || j == 0) {
                    t1[i][j] = true;
                    d1.addLast(new int[]{i, j});

                }
                if (i == w - 1 || j == h - 1) {
                    t2[i][j] = true;
                    d2.addLast(new int[]{i, j});
                }
            }
        }
        bfs(d1, t1);
        bfs(d2, t2);
        List<List<Integer>> anwser = new ArrayList<>();
        // 对两种情况的结果集求交集
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if (t1[i][j] && t2[i][j]) {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    anwser.add(list);
                }
            }
        }
        return anwser;
    }
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private void bfs(Deque<int[]> d, boolean[][] t) {
        while (!d.isEmpty()) {
            // 当前单元格坐标、值
            int[] info = d.pollFirst();
            int x = info[0];
            int y = info[1];
            int v = grid[x][y];
            for (int[] di : dirs) {
                // 移动后的新单元格的坐标、值
                int nx = x + di[0], ny = y + di[1];
                // 超出范围跳过
                if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
                // 无法流向新单元格或者新单元格本身是true，跳过
                if (grid[nx][ny] < v || t[nx][ny]) continue;
                d.addLast(new int[]{nx, ny});
                t[nx][ny] = true;
            }
        }
    }

    public static void main(String[] args) {
        int[][] 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}};
        List<List<Integer>> lists = new Solution().pacificAtlantic(heights);
        System.out.println(lists);
    }
}

运行结果