# 太平洋大西洋水流问题

大一 -> 大二暑期算法作业

分站已经上线简约风算法作业集合（也可以选择阅读模式

# 看到题目的感想

刚看到这个题目的时候感觉他不是很熟悉，没有见过类似的题目，也没有见过类似的场景，感觉有点意思。

题目不算很长，但感觉难度不小。

# 题目描述

给定一个 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]] (上图中带括号的单元). （序号先左后上）

# 题目解答

（**ps：** 由于做题时采用的是执行代码，并未提交，提交结果均为后来补上，所以时间均为两天前）

# 逆流而上

最开始的名字叫逆着水流向上找，后面才想起来有逆流而上这个成语，才改了名字。

最开始浮现的思路是想暴力解题，后来发现暴力解题太过于麻烦，效率也不高，索性就放弃了。之后才有的现在这个想法。

# （1）解题思路

本题找的是能够让水流留到两片水域的陆地单元的位置坐标，那么既然水能过去，那我们反过来找，分别找到两个水域的水能流到的地方，之后取交集，就得到了我们想要的答案。

# （2）代码

配合题目链接食用

# Java

注：这个代码在 idea 上可以正常运行，但在力扣上会有报错。报错如下：

error: incompatible types: List<int[]> cannot be converted to List<List> [in Driver.java]

List<List> ret = new Solution().pacificAtlantic(param_1);

List & ArrayList：https://www.jianshu.com/p/25aa92f8d681 来源：简书

class Solution {

            public List<int[]> pacificAtlantic(int[][] matrix) {
                List<int[]> ret = new ArrayList<>(); // 储存最终数据
                int m = matrix.length; // 获取矩阵一边的长度
                if(m < 1) return ret; // 矩阵大小为0时
                int n = matrix[0].length; // 获取矩阵另一边的长度
                boolean[][] Pacific = new boolean[m][n]; // 太平洋的
                boolean[][] Atlantic = new boolean[m][n]; // 大西洋的

                for(int i = 0; i < m; i++) { // 递归判断一条边
                    dfs(matrix, i, 0, Pacific, matrix[i][0]);
                    dfs(matrix, i, n-1, Atlantic, matrix[i][n-1]);
                }
                for(int i = 0; i < n; i++) { // 递归判断另一条边
                    dfs(matrix, 0, i, Pacific, matrix[0][i]);
                    dfs(matrix, m-1, i, Atlantic, matrix[m-1][i]);
                }

                for(int i = 0; i < m; i++) { // 取交集得到最终结果
                    for(int j = 0; j < n; ++j)
                        if(Pacific[i][j] && Atlantic[i][j])
                            ret.add(new int[]{i, j}); // 放入数据
                }
                return ret; // 返回结果
            }

            private void dfs(int[][] m, int x, int y, boolean[][] visited, int pre) {
                // 超出边界 或 判断过是可以的 或 不能继续向上流动，则返回
                if(x < 0 || y < 0 || x >= m.length || y >= m[0].length || visited[x][y] || m[x][y] < pre)
                    return;
                visited[x][y] = true; // 可以向上流
                dfs(m, x+1, y, visited, m[x][y]); // 递归判断相邻行或列
                dfs(m, x-1, y, visited, m[x][y]); // 递归判断相邻行或列
                dfs(m, x, y+1, visited, m[x][y]); // 递归判断相邻行或列
                dfs(m, x, y-1, visited, m[x][y]); // 递归判断相邻行或列
            }
        }