题目

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

在这里插入图片描述

解题思路

这题和130题有点类似，都是从边界往内寻找。

这题呢我们从边界出发，假设先从上边出发，也就是太平洋。靠近上边的水流一定都可以流入太平洋，那么我们只需要将“上边”遍历，找到高度比它高的，就可以通过它流入太平洋。其它三条边也是这样。只不过右边和下边是可以流入大西洋。

解释一下：题目说高度高的可以向高度低的或者高度相等的流动。也就是说，只要比上边的水流的高度高，或者相等，那么该水流就可以流到上边，而上边又和太平洋相连，即该水流可流入太平洋。

这样，两轮循环，一轮用来找到可以流入太平洋的水流，一轮找到可以流入大西洋的水流，把它们分别放入两个boolean数组中，然后再来一次整个数组遍历，如果有一个水流即可流入太平洋也可流入大西洋（toPa[i][j] && toAt[i][j]）。那么它就是我们要寻找的。把它的坐标放入res，返回即可。

本题的重点就是中间的水流可以通过四条边的水流流入对应的海洋。

代码

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<>();

        if (matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }

        int r = matrix.length;//行数，可以看成y轴
        int c = matrix[0].length;//列数，可以看成x轴
        boolean[][] toPa = new boolean[r][c];
        boolean[][] toAt = new boolean[r][c];

        for (int i = 0; i < r; i++) {//要去选择第一列和最后一列，  变化的是行数，列数是固定的0和c-1，所以这里循环条件用行（r）
            //第一次遍历，会给一个初始高度，到后面要进行比较的时候再用matrix[r][c] 来替换初始高度
            DFS(i, 0, matrix, toPa, Integer.MIN_VALUE);//遍历第一列  即正方形的左边，它用DFS来遍历哪些能够通过它 ，到达太平洋（Pa）的水流。下面的同理
            DFS(i, c - 1, matrix, toAt, Integer.MIN_VALUE);//遍历最后一列
        }

        for (int i = 0; i < c; i++) {
            DFS(0, i, matrix, toPa, Integer.MIN_VALUE);//遍历第一行
            DFS(r - 1, i, matrix, toAt, Integer.MIN_VALUE);//遍历最后一行
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {//遍历整个二维数组
                if (toPa[i][j] && toAt[i][j]) {//如果该水流即能到达pa也能到达at，就是我们的目标
                    List<Integer> cur = new ArrayList<>();
                    cur.add(i);
                    cur.add(j);
                    res.add(cur);
                }
            }
        }
        return res;
    }

    int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public void DFS(int r, int c, int[][] matrix, boolean[][] toSea, int height) {
        if (r < 0 || r >= matrix.length
                || c < 0 || c >= matrix[0].length
                || toSea[r][c]
                || matrix[r][c] < height) {//matrix[r][c] < height即现在遍历到的水流高度，比之前那个要小，这是不可以的，因为只有现在的高度大于之前的高度，才可以通过之前的流入海洋
            return;
        }
        toSea[r][c] = true;//它能够到达大西洋或者太平洋。要根据具体是那个在那个循环调用的。
        for (int[] dir : directions) {
            /*
            r + dir[0]：相当于横坐标向四个方向遍历
            c + dir[1]：相当于纵坐标向四个方向遍历
             */
            DFS(r + dir[0], c + dir[1], matrix, toSea, matrix[r][c]);//这时候高度就会更新为matrix[r][c]
        }

    }
}