LeetCode Daily Problem P417: Pacific Atlantic Water Flow

---

Timeline

Timeline

2025-10-05

init

Multi-source BFS

---

Problem:

P417 Pacific Atlantic Water Flow problem

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

Multi-source BFSIt is to start BFS from multiple starting points (sources) at the same time. The key idea is to put multiple source points into the queue as the initial layer (layer 0), and then one BFS expands them outward simultaneously. This is equivalent to all source points spreading waves together, and the layer number when each node is first visited is the shortest distance to the nearest source.

If ordinary BFS is used for this problem, a BFS must be done for each vertex, so multi-source BFS is better. That is, if a cell can flow to an ocean (Pacific or Atlantic), then its higher neighbors must also be able to flow to the ocean that this cell can reach.
During initialization, enqueue all points on the island’s coast, i.e., all cells on the boundary. Each time a cell is dequeued, if a neighbor of this cell has a height higher than this cell, then the ocean that this cell can reach can also be reached by that neighbor.
The key issue is how to handle duplicates. Each cell has two states. Only when these two states are fixed and confirmed that they will not change is the processing complete. Therefore, if during the processing of the four neighbors a neighbor’s state does not change, do not enqueue it; enqueue the neighbors whose state has changed.

#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;

    // First row and last row
    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});
    }
    // First column and last column
    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();
      // If it can reach the ocean, then its higher neighbors can also reach it.
      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;
          }

          // Add neighbors to the queue; only add them when the neighbor's state has changed.
          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;
  }
};