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

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

题目描述

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

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

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

提示：

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

示例：

给定下面的 5x5 矩阵:

太平洋 ~ ~ ~ ~ ~

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]] (上图中带括号的单元).

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解题过程

解题思路

动态规划：与“岛屿数量“类似。但是本题解题时要逆向思考，将“水往低处流”转变为“水往高处走”。从两大洋的边界出发开始搜索，分别记录各自能够到达的点。最后遍历寻找两大洋同时能流到的坐标即可。
注意：递归函数几乎和岛屿数量一样，只不过多了流动的条件（从低往高流）。

class Solution {
    int [] direction = {-1, 0, 1, 0, -1};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {

        //反其道而行，水往低处流转换为水从两大洋往陆地流，能逆着流到的陆地，反过来就可以往两大洋流；
        //因此从两大洋的四条边开始往上搜索

        List<List<Integer>> list = new ArrayList<>();
        boolean [][] canReachT = new boolean[heights.length][heights[0].length];
        boolean [][] canReachD = new boolean[heights.length][heights[0].length]; 
        int m = heights.length;
        int n = heights[0].length;
        for(int i = 0; i < m; i++){
            dfs(i, 0, canReachT, heights);
            dfs(i, n - 1, canReachD, heights);
        }

        for(int i = 0; i < n; i++){
            dfs(0, i, canReachT, heights);
            dfs(m - 1, i, canReachD, heights);
        }

        //两大洋都能流到的地方就是TM的要求的坐标点
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(canReachT[i][j] && canReachD[i][j]){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    list.add(temp);
                }
            }
        }
        return list;

    }

    void dfs(int i, int j, boolean [][] reachDaYang, int[][] heights){
        if(reachDaYang[i][j]){//已经到达过了，或者说访问过了，就直接返回
            return;
        }

        reachDaYang[i][j] = true;
        int x, y;
        for(int k = 0; k < 4; k++){
            x = i + direction[k];
            y = j + direction[k + 1];
            if(x >= 0 && x < heights.length 
            && y >= 0 && y < heights[0].length
            && heights[i][j] <= heights[x][y]){
                            dfs(x, y, reachDaYang, heights);
                        }
        }
        
    }


}

总结