[数据结构与算法]LeetCode417—太平洋大西洋水流问题（java版）

题目描述：

标签：深度优先搜索? 广度优先搜索? 数组? 矩阵

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

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

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

代码：

?思路分析：

1、设置两个boolean数组canReachP和canReachA记录每个水流是否能流入太平洋或者大西洋。

2、从能直接接触到太平洋和大西洋的上下左右边界开始进行dfs搜索，修改对应的boolean数组。

3、定义dfs方法，如果当前水流能流入则返回，否则更改boolean值，并对上下左右四个方向继续进行遍历，如果当前坐标不合理且下一个点的高度<当前高度，则跳过这个点，否则沿着这个点继续进行dfs搜索。

class Solution {
    private int m,n;
    private int[][] heights;
    private int[][] direction = {{0,1},{0,-1},{1,0},{-1,0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> ans = new ArrayList<>();
        if(heights == null || heights.length == 0){
            return ans;
        }
        m = heights.length;
        n = heights[0].length;
        this.heights = heights;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];

        for(int i = 0;i < m;i++){
            dfs(i, 0, canReachP);
            dfs(i, n-1, canReachA);
        }

        for(int i = 0;i < n;i++){
            dfs(0, i, canReachP);
            dfs(m-1, i, canReachA);
        }

        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(canReachP[i][j] && canReachA[i][j]){
                    ans.add(Arrays.asList(i,j));
                }
            }
        }
        return ans;
    }

    private void dfs(int r, int c,boolean[][] canReach){
        if(canReach[r][c]){
            return;
        }
        canReach[r][c] = true;
        for(int[] d : direction){
            int nextR = r + d[0];
            int nextC = c + d[1];
            if(nextR < 0 || nextR >= m || nextC < 0 || nextC >= n 
                || heights[r][c] > heights[nextR][nextC]){
                continue;
            }
            dfs(nextR, nextC, canReach);
        }
    }
}

?