10-08-2026 继续刷题打卡

417. Pacific Atlantic Water Flow
一开始写的时候是从每个位置计算是否可以流水到海里，后来ai提醒我说，时间复杂度太高了，因此改为从海边倒流逆向计算哪些位置的水可以流到海里，每个海跑一遍BFS/DFS 就行了。
第一遍写的时候左上角和右下角的位置，重复放入queue里面了，需要注意。
还有就是两个ocean 要处理两遍，visited 和queue 都需要重置，在调用函数的时候把参数设为引用。

class Solution {
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
public:
vector> pacificAtlantic(vector>& heights) {
int m = heights.size(), n = heights[0].size();
vector> waterFlow(m, vector(n, 0));
vector> visited(m, vector(n, false));
queue> q;
for (int i = 0; i < m; i++) {
waterFlow[i][0]++;
visited[i][0] = true;
q.push({i, 0});
}
for (int j = 1; j < n; j++) {
waterFlow[0][j]++;
visited[0][j] = true;
q.push({0, j});
}
bfs(heights, waterFlow, visited, q);

visited = vector>(m, vector(n, false));
for (int i = 0; i < m; i++) {
waterFlow[i][n-1]++;
visited[i][n-1] = true;
q.push({i, n-1});
}
for (int j = 0; j < n - 1; j++) {
waterFlow[m-1][j]++;
visited[m-1][j] = true;
q.push({m-1, j});
}
bfs(heights, waterFlow, visited, q);

vector> res;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (waterFlow[i][j] == 2) {
res.push_back({i, j});
}
}
}
return res;
}

void bfs(vector>& heights, vector>& waterFlow, vector>& visited, queue>& q) {
int m = heights.size(), n = heights[0].size();
while(!q.empty()) {
auto [cur_row, cur_col] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nbr_row = cur_row + dr[k];
int nbr_col = cur_col + dc[k];
if (nbr_row < 0 || nbr_col < 0 || nbr_row >= m || nbr_col >= n) continue;
if (visited[nbr_row][nbr_col]) continue;
if (heights[nbr_row][nbr_col] >= heights[cur_row][cur_col]) {
waterFlow[nbr_row][nbr_col]++;
visited[nbr_row][nbr_col] = true;
q.push({nbr_row, nbr_col});
}
}
}
}
};