有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
示例 1：
输入: heights = [[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]]示例 2：
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]提示：
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105
解题思路：正难则反
刚拿到这道题的时候，第一思路就是想暴力枚举所有的元素，以每个元素为入口进行一次深度优先遍历，并且判断一下是否存在流向大西洋和太平洋的位置，是的话则加入结果集！
这个思路确实是可以的，但是在这道题中有规模很大的矩阵，此时就会超时了，因为当我们遍历一个元素进行深度优先遍历之后，我们遍历下一个元素再次进行深度优先遍历的时候，此时可能会重复了之前走过的一些路径，也就是说，我们这种方法存在着大量的重复遍历，导致超时，所以我们必须换个思路！
正难则反，既然我们从高处向低处找路径会超时，那么我们试试从低处往高处找！
不过有一个问题，就是如果我们是从低处往高处找的话，因为我们要找的是流向两个洋的，那么我们只能从单个洋的低处往上找到高处，所以我们需要分别对太平洋和大西洋的低处开始向上找，而没办法同时处理流向两个洋的情况！
又因为 i = 0 和 j = 0 是太平洋低处的位置，所以我们就从符合这两个坐标的位置处开始向上找流向太平洋的路径，然后用一个布尔值类型的二维数组 pacific_used 标记走过的路径，表示这是可以从高处流向太平洋的路径！
而 i = m - 1 和 j = n - 1（这里 m、n 分别表示岛屿的长和宽）是大西洋低处的位置，我们同样从符合这两个坐标的位置处开始向上找流向大西洋的路径，然后用一个布尔值类型的二维数组 atlantic_used 标记走过的路径，表示这是可以从高处流向大西洋的路径！
此时重点来了，我们遍历两个布尔值数组，判断两个数组中是否存在位置都为 true 的，存在的话说明从这个位置是可以同时流向两个洋，则添加到结果集中，如果不存在的话则不需要处理，最后返回结果集即可！
而对于其中向高处寻找路径的递归函数就不再赘述了，比较简单，就是一些边界条件要处理好，防止越界即可！
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size();
int n = heights[0].size();
// 1. 先处理太平洋
vector<vector<bool>> pacific_used(m, vector<bool>(n, false));
for(int i = 0; i < m; ++i) dfs(heights, i, 0, pacific_used);
for(int j = 0; j < n; ++j) dfs(heights, 0, j, pacific_used);
// 2. 再处理大西洋
vector<vector<bool>> atlantic_used(m, vector<bool>(n, false));
for(int i = 0; i < m; ++i) dfs(heights, i, n - 1, atlantic_used);
for(int j = 0; j < n; ++j) dfs(heights, m - 1, j, atlantic_used);
// 3. 判断两个标记数组中是否存在都为true的，是的话说明可以同时流向两个洋，则添加到结果集中
vector<vector<int>> ret;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
if(pacific_used[i][j] && atlantic_used[i][j])
ret.push_back({ i, j });
return ret;
}
void dfs(vector<vector<int>>& heights, int x, int y, vector<vector<bool>>& used)
{
// 标记为已走过，然后根据边界情况进行递归处理
used[x][y] = true;
if(x + 1 < heights.size() && heights[x + 1][y] >= heights[x][y] && used[x + 1][y] == false)
dfs(heights, x + 1, y, used);
if(y + 1 < heights[0].size() && heights[x][y + 1] >= heights[x][y] && used[x][y + 1] == false)
dfs(heights, x, y + 1, used);
if(x - 1 >= 0 && heights[x - 1][y] >= heights[x][y] && used[x - 1][y] == false)
dfs(heights, x - 1, y, used);
if(y - 1 >= 0 && heights[x][y - 1] >= heights[x][y] && used[x][y - 1] == false)
dfs(heights, x, y - 1, used);
}
};