本文首发于馆主君晓的博客，04-27每日一题
题目描述
??题目链接，417. 太平洋大西洋水流问题，题目截图如下：
题目分析
??这道题目通俗来讲就是，现在有一个二维数组，数组里的值代表着比海平面高出多少。对于一个二维数组而言，左边和上边与太平洋相接，而右边和下边与大西洋相接。只要与海相接雨水都能够流进大海。而在这个二维数组中，如果一个格子的值大于相邻格子的值，那么雨水就能够从本格子流到相邻的格子（水往低处流）。现在需要找到这个二维数组中，哪些格子里的雨水既可以流入太平洋，有可以流入大西洋。
??经过上述分析之后，那么自然而然就能够想到使用深度优先搜索了。我们的思路是，从二维数组的四个边界出发，寻找上升序列，从太平洋边界出发的，到达的地方我们用二维布尔数组记录。同样从大西洋边界出发的，到达的地方我们用另外一个布尔数组记录。最后我们只需要取这两个数组的交集即可。
??而在遍历的时候就是我们通用的深度优先遍历的方法了，定义方向数组，枚举起点，然后每次dfs的时候判断下标是否有效并且是否被访问过，然后在dfs中递归调用dfs。
代码实现
??c++代码如下：
class Solution {
// 行数和列数
int rows = 0,cols = 0;
// 返回的结果
vector<vector<int>> res;
// 上右下左四个方向
int direction[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
// 深度优先搜索
rows = heights.size();
cols = heights[0].size();
vector<vector<bool>> pacific(rows,vector<bool>(cols));
vector<vector<bool>> atlantic(rows,vector<bool>(cols));
for(int i=0;i<rows;i++){
pacific[i][0] = true;
dfs(i,0,heights,pacific);
}
for(int i=0;i<cols;i++){
pacific[0][i] = true;
dfs(0,i,heights,pacific);
}
for(int i=0;i<cols;i++){
atlantic[rows-1][i] = true;
dfs(rows-1,i,heights,atlantic);
}
for(int i=0;i<rows;i++){
atlantic[i][cols-1] = true;
dfs(i,cols-1,heights,atlantic);
}
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(pacific[i][j] && atlantic[i][j]){
vector<int> tmp;
tmp.push_back(i);
tmp.push_back(j);
res.push_back(tmp);
}
}
}
return res;
}
void dfs(int x,int y,vector<vector<int>> &heights,vector<vector<bool>> &record){
for(int i = 0;i<4;i++){
int xx = x+direction[i][0];
int yy = y+direction[i][1];
if(xx>=0 && xx<rows && yy>=0 && yy<cols && !record[xx][yy] && heights[xx][yy]>=heights[x][y]){
record[xx][yy] = true;
dfs(xx,yy,heights,record);
}
}
}
};
结语
??我要一步一步往上爬，在最高点乘着叶片往前飞~
