DFS
思路
见: https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/shui-wang-gao-chu-liu-by-xiaohu9527-xxsx/
思路是一样的但是我不会实现(不知道是脑子抽了还是长时间没练的缘故)
代码
class Solution {
public:
vector<vector<int>> P,A,ans;
int m,n;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void dfs(vector<vector<int>> &heights,vector<vector<int>> &visited,int x,int y)
{
if(visited[x][y]) return;
visited[x][y]=1;
if(P[x][y]&&A[x][y])
ans.push_back({x,y});
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n&&heights[nx][ny]>=heights[x][y])
dfs(heights,visited,nx,ny);
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
m=heights.size(),n=heights[0].size();
P=A=vector<vector<int>>(m,vector<int>(n,0));
for(int i=0;i<n;i++)
{
dfs(heights,P,0,i);
dfs(heights,A,m-1,i);
}
for(int i=0;i<m;i++)
{
dfs(heights,P,i,0);
dfs(heights,A,i,n-1);
}
return ans;
}
};