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

Code

//思路：分别利用两个二维数组，分别标记从各自的边缘通过dfs能够逆流到的位置
//最后对比两个表，相交的点就是所求坐标
//time complexity:O(2^n)
//space complexity:O(2nxm)
class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if(matrix.empty())return res;
        int row=matrix.size(),col=matrix[0].size(),i,j;
        vector<vector<bool>> pacifics(row, vector<bool>(col, 0));//能到太平洋的坐标
        vector<vector<bool>> atlantics(row, vector<bool>(col, 0));//能到大西洋的坐标
        //逆向思维，从太平洋大西洋的边缘进入，
        for(int i = 0; i < row; i++){
            DFS(matrix, i, 0, matrix[i][0], pacifics);
            DFS(matrix, i, col-1, matrix[i][col-1], atlantics);
        }
        for(int j = 0; j < col; j++){
            DFS(matrix, 0, j, matrix[0][j], pacifics);
            DFS(matrix, row-1, j, matrix[row-1][j], atlantics);
        }

        // 既能 touch pacific 又能 touch atlantic 的 grid 放进结果中
        vector<vector<int>> res;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //若该点两大洋重合，则加入res
                if (pacifics[i][j] && atlantics[i][j]) {
                    res.push_back({ i, j });
                }
            }
        }
        return res;
    }

    // 逆流而上， 标记能流到的地方
    void DFS(vector<vector<int>> & matrix, int i, int j, int pre, vector<vector<bool>> & ocean){
        //边缘检测，直接返回
        if(i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size()) return;
        //已经流经过
        if(ocean[i][j]) return;
        //因为是逆向，所以是<就返回
        if(matrix[i][j] < pre) return;
        ocean[i][j] = true;
        //四个方向递归
        DFS(matrix, i+1, j, matrix[i][j], ocean);
        DFS(matrix, i-1, j, matrix[i][j], ocean);
        DFS(matrix, i, j+1, matrix[i][j], ocean);
        DFS(matrix, i, j-1, matrix[i][j], ocean);
    }
};