417. 太平洋大西洋水流问题

开始的思路：

遍历每个点，进行递归搜索，然后记录下能够到达太平洋和大西洋的点，从别的点再次遍历到能达到的点时，直接返回（因为遍历到的点能够到大西洋和太平洋，所以该点也能到，就不用递归了）

然后，超时！！！

其实有个小技巧，就是直接从四个边界的点开始搜索，凡是从上边界和左边界能搜索到的，都是能达到太平洋的，凡是从下边界和右边界能搜索到的，都是能到达大西洋的，然后两个记录的数组进行对比，直接就能得出来能到达大西洋和太平洋的点

代码：

class Solution{

    List<List<Integer>> res = new LinkedList<>();

    // 太平洋，凡是能走到的点，都是能到太平洋得点
    public void trace(int i, int j, int[][]matrix, int data, boolean tpy[][]){

        // 出口
        if(i < 0 || j < 0 || j >= matrix[0].length || i >= matrix.length){
            return;
        }

        // 凡是之前到达过的，直接返回即可
        if(tpy[i][j]){
            return;
        }

        // 能到达的点的条件
        // 1、当前值比data要大 2、凡是标记过的都记录下来
        if(matrix[i][j] >= data && !tpy[i][j]) {
            // 1、记录下来
            tpy[i][j] = true;
            // 2、继续遍历
            trace(i-1, j, matrix, matrix[i][j], tpy);
            trace(i+1, j, matrix, matrix[i][j], tpy);
            trace(i, j-1, matrix, matrix[i][j], tpy);
            trace(i, j+1, matrix, matrix[i][j], tpy);
            // tpy[i][j] = false;
        }
    }

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {

        boolean tpy[][] = new boolean[matrix.length][matrix[0].length];
        boolean dxy[][] = new boolean[matrix.length][matrix[0].length];

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

        // 从边界出发
        for(int i=0; i<matrix.length; i++){
            // 太平洋
            int a = matrix[i][0];
            trace(i, 0, matrix, a, tpy);

            // 大西洋
            int b = matrix[i][matrix[0].length-1];
            trace(i, matrix[0].length-1, matrix, b, dxy);
        }


        for(int i=0; i<matrix[0].length; i++){
            // 太平洋
            int a = matrix[0][i];
            trace(0, i, matrix, a, tpy);
            // 大西洋
            int b = matrix[matrix.length-1][i];
            trace(matrix.length-1, i, matrix, b, dxy);
        }


        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                if(tpy[i][j] && dxy[i][j]){
                   //  System.out.println(i + " " + j);
                    List<Integer> ls = new LinkedList<>();
                    ls.add(i);
                    ls.add(j);
                    res.add(ls);
                }
            }
        }

        return res;
    }


    public static void main(String[] args) {
        Solution s = new Solution();
        s.pacificAtlantic(new int[][]{{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}});
    }

}