题目:417. 太平洋大西洋水流问题
思路
代码
(1) MyMothed
// 符合条件的点 : 既可以到达左或上边界,也可以到达右或下边界;
class Solution {
private:
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<int>> result;
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y)
{
int i, j;
int next_x, next_y;
int m = heights.size(), n = heights[0].size();
for(i = 0; i < 4; i++)
{
next_x = x + dir[i][0];
next_y = y + dir[i][1];
if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n)
{
continue;
}
if(!visited[next_x][next_y] && heights[next_x][next_y] <= heights[x][y])
{
visited[next_x][next_y] = true;
dfs(heights, visited, next_x, next_y);
}
}
}
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int i, j;
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> visited_P(m, vector<bool>(n, false)); // Pacific Ocean
vector<vector<bool>> visited_A(m, vector<bool>(n, false)); // Atlantic Ocean
result.clear();
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
heights[i][j] = -heights[i][j];
}
}
// Pacific
i = 0;
for(j = 0; j < n; j++)
{
if(!visited_P[i][j])
{
visited_P[i][j] = true;
dfs(heights, visited_P, i, j);
}
}
j = 0;
for(i = 0; i < m; i++)
{
if(!visited_P[i][j])
{
visited_P[i][j] = true;
dfs(heights, visited_P, i, j);
}
}
// Atlantic
i = m-1;
for(j = 0; j < n; j++)
{
if(!visited_A[i][j])
{
visited_A[i][j] = true;
dfs(heights, visited_A, i, j);
}
}
j = n-1;
for(i = 0; i < m; i++)
{
if(!visited_A[i][j])
{
visited_A[i][j] = true;
dfs(heights, visited_A, i, j);
}
}
cout << "P" << endl;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
cout << visited_P[i][j] << ", ";
}
cout << endl;
}
cout << "A" << endl;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
cout << visited_A[i][j] << ", ";
}
cout << endl;
}
// 能重合的地方就是想要的点
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
if(visited_P[i][j] && visited_A[i][j])
{
result.push_back({i, j});
}
}
}
return result;
}
};
把海拔翻转一下,分别统计从太平洋能流经的地盘和大西洋能流经的地盘,这两个地盘的重合部分就是题目所求;