417. 太平洋大西洋水流问题
题目链接:417. 太平洋大西洋水流问题
代码如下:
class Solution
{
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
{
vector<vector<int>> res;
//记录从太平洋出发,可以遍历的节点
vector<vector<bool>> pacific(heights.size(),vector<bool>(heights[0].size(),false));
//记录从大西洋出发,可以遍历的节点
vector<vector<bool>> atlantic(heights.size(),vector<bool>(heights[0].size(),false));
//从最上最下行的节点出发,向高处遍历
for(int i=0;i<heights.size();i++)
{
dfs(heights,pacific,i,0);//遍历最左列,接触太平洋
dfs(heights,atlantic,i,heights[0].size()-1);//遍历最右列,接触大西洋
}
//从最左最右列的节点出发,向高处遍历
for(int j=0;j<heights[0].size();j++)
{
dfs(heights,pacific,0,j);//遍历最上行,接触太平洋
dfs(heights,atlantic,heights.size()-1,j);//遍历最下行,接触大西洋
}
for(int i=0;i<heights.size();i++)
{
for(int j=0;j<heights[0].size();j++)
{
if(pacific[i][j]&&atlantic[i][j]) res.push_back({i,j});
}
}
return res;
}
private:
int dirX[4]{0,0,-1,1};//上下左右
int dirY[4]{-1,1,0,0};//上下左右
//深度优先遍历
void dfs(vector<vector<int>>& heights,vector<vector<bool>>& visited,int x,int y)
{
if(visited[x][y]) return;
visited[x][y]=true;
for(int i=0;i<4;i++)
{
int nextX=x+dirX[i],nextY=y+dirY[i];
//越界
if(nextX<0||nextX>=heights.size()||nextY<0||nextY>=heights[0].size())
continue;
if(heights[x][y]>heights[nextX][nextY]) continue;
dfs(heights,visited,nextX,nextY);
}
}
//广度优先搜索
void bfs(vector<vector<int>>& heights,vector<vector<bool>>& visited,int x,int y)
{
queue<pair<int,int>> que;
visited[x][y]=true;
que.push({x,y});
while(!que.empty())
{
auto cur=que.front();
que.pop();
for(int i=0;i<4;i++)
{
int nextX=x+dirX[i],nextY=y+dirY[i];
//越界
if(nextX<0||nextX>=heights.size()||nextY<0||nextY>=heights[0].size())
continue;
if(heights[x][y]>heights[nextX][nextY]) continue;
visited[nextX][nextY]=true;
que.push({nextX,nextY});
}
}
}
};