一、题目
二、思路
（1）找出从太平洋出发的水所能到达的点：
（2）找出所有从大西洋出发的水能到达的点（从低到高）：
（3）找出1和2的重合点：
（1）其实满足条件的点中，其从对应的海洋到该点的路线可能是有多条的，但是注意我们只需要找到满足条件的点，而不是找出所有路线。所以可以遍历到当前节点时就用canReach数组进行标记（标记为true，确定遍历过），这种情况就是找到一条路线即可。
（2）ps：一开始两个for循环的边界的col和row写反了，导致heap overflow报错，细心。
三、代码
class Solution { private: vector<pair<int, int>>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { if(heights.empty() || heights[0].empty()){ return {}; } int row = heights.size();//row行数 int col = heights[0].size();//col列数 vector<vector<int>> ans; //太平洋 vector<vector<bool>> canReachP(row, vector<bool>(col, false)); //大西洋 vector<vector<bool>> canReachA(row, vector<bool>(col, false)); for(int i = 0; i < row; i++){ //左边太平洋 dfs(heights, canReachP, i, 0); //右边大西洋 dfs(heights, canReachA, i, col - 1); } for(int j = 0; j < col; j++){ //上边太平洋 dfs(heights, canReachP, 0, j); //下边大西洋 dfs(heights, canReachA, row - 1, j); } for(int i = 0; i < row; i++){ for(int j =0; j < col; j++){ if(canReachP[i][j] && canReachA[i][j]){ ans.push_back({i, j}); } } } return ans; } void dfs(vector<vector<int>>& heights, vector<vector<bool>>& canReach, int x, int y){ if(canReach[x][y]){ return; } canReach[x][y] = true; for(auto dir: directions){ int newx = x + dir.first, newy = y + dir.second; if(canReachfun(heights, x, y, newx, newy)){ dfs(heights, canReach, newx, newy); } } } bool canReachfun(vector<vector<int>>& heights,int x,int y, int newx, int newy){ //判断点是否在网格内,且符合题目要求 if(newx>=0 && newx<heights.size() && 0<=newy && newy<heights[0].size() && heights[x][y] <= heights[newx][newy]){ return true; }else{ return false; } } };
