leetcode每日一题 P417 太平洋大西洋水流问题

---

时间轴

时间轴

2025-10-05

init

多源BFS

---

题目：

P417 太平洋大西洋水流问题

https://leetcode.cn/problems/pacific-atlantic-water-flow/description/?envType=daily-question&envId=2025-10-05

多源 BFS就是从多个起点（sources）同时开始 BFS。它的关键思想是：把多个“源点”都放入队列作为初始层（第 0 层），然后一次 BFS 把它们同时向外扩展。这相当于所有源点一起“扩散波动”，每个节点第一次被访问到的层数就是到最近源点的最短距离。

这个题如果用普通 BFS 要对每个顶点都得做一次 BFS，因此用多源 BFS 会更好，即如果一个单元格能流到某海洋(太平洋或大西洋)那么高于它的邻居必定也能流到该单元格能到达的海洋。初始化时让岛岸边的所有点入队，即边界上的所有单元格，每次出队一个单元格，如果该单元格的邻居中高度高于该单元格的，那么该单元格能到达的海洋，这个邻居也能到达。关键问题是如何处理重复的问题，每个单元格有两个状态，只有固定了这两个状态，确定这两个状态不会改变了，才是处理完成的。因此如果在四个邻居的处理中某个邻居的状态没有发生改变，就不让它入队，将发生状态改变的邻居入队。

#include <queue>
#include <utility>
#include <vector>

using std::pair;
using std::queue;
using std::vector;

class Solution {
public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
    int m = heights.size(), n = heights[0].size();
    int i, j, k;
    int neighbor_i, neighbor_j;
    // (i-1, j) (i,j+1) (i+1,j)  (i,j-1)
    int arr[] = {-1, 0, 1, 0, -1};
    queue<pair<int, int>> que;
    vector<vector<pair<int, int>>> vec(m, vector<pair<int, int>>(n, {-1, -1}));
    bool updated = false;
    vector<vector<int>> result;

    // 第一行和最后一行
    for (int j = 0; j < n; j++) {
      vec[0][j].first = 1;
      vec[m - 1][j].second = 1;
      que.push({0, j});
      que.push({m - 1, j});
    }
    // 第一列和最后一列
    for (int i = 0; i < m; i++) {
      vec[i][0].first = 1;
      vec[i][n - 1].second = 1;
      que.push({i, 0});
      que.push({i, n - 1});
    }

    while (!que.empty()) {
      i = que.front().first;
      j = que.front().second;

      que.pop();
      // 可以到Ocean，那么高于它的邻居也可以到
      for (k = 0; k <= 3; k++) {
        neighbor_i = i + arr[k];
        neighbor_j = j + arr[k + 1];
        updated = false;
        if ((neighbor_i >= 0 && neighbor_i < m && neighbor_j >= 0 &&
             neighbor_j < n) &&
            heights[neighbor_i][neighbor_j] >= heights[i][j]) {

          if (vec[i][j].first == 1 && vec[neighbor_i][neighbor_j].first != 1) {
            vec[neighbor_i][neighbor_j].first = 1;
            updated = true;
          }
          if (vec[i][j].second == 1 &&
              vec[neighbor_i][neighbor_j].second != 1) {
            vec[neighbor_i][neighbor_j].second = 1;
            updated = true;
          }

          // 邻居加入que，只有当邻居状态被改变时才加入
          if (updated) {
            que.push({neighbor_i, neighbor_j});
          }
        }
      }
    }

    for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++) {
        if (vec[i][j].first == 1 && vec[i][j].second == 1) {
          result.push_back({i, j});
        }
      }
    }

    return result;
  }
};