# Easy-to-understand C++ solution using BFS with priority_queue.

• Similar to the trapping rain water problem: https://leetcode.com/problems/trapping-rain-water-ii.

``````struct Cell {
int row, col, height;
Cell(int r, int c, int h): row(r), col(c), height(h) {}
bool operator<(const Cell& cell) const {
return height > cell.height;
}
};

const int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

// BFS with priority_queue
class Solution {
private:
void visit(priority_queue<Cell> &aQueue, vector<vector<bool>> &visited, vector<vector<bool>> &canFlow, const vector<vector<int>> &matrix) {
int m = matrix.size();
int n = matrix[0].size();
while (!aQueue.empty()) {
Cell aCell = aQueue.top();
aQueue.pop();
int nextR, nextC, nextH;
for (auto &dir : directions) {
nextR = aCell.row + dir[0];
nextC = aCell.col + dir[1];
if (nextR>=0 && nextR < m && nextC >=0 && nextC < n && !visited[nextR][nextC]) {
visited[nextR][nextC] = true;
nextH = matrix[nextR][nextC];
if (nextH >= aCell.height) {
visited[nextR][nextC] = true;
canFlow[nextR][nextC] = true;
Cell next(nextR, nextC, nextH);
aQueue.push(next);
}
}
}
}
}
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
priority_queue<Cell> aQueue;
int m = matrix.size();
int n = matrix[0].size();
// can flow into the pacific ocean
vector<vector<bool>> can1(m, vector<bool> (n, false));
// can flow into the atlantic ocean
vector<vector<bool>> can2(m, vector<bool> (n, false));
vector<vector<bool>> visited(m, vector<bool> (n, false));

// push the top and left boundary
for (int i=0; i<m; ++i) {
can1[i][0] = true;
visited[i][0] = true;
aQueue.push(Cell(i, 0, matrix[i][0]));
}

for (int i=1; i<n; ++i) {
can1[0][i] = true;
aQueue.push(Cell(0, i, matrix[0][i]));
visited[0][i] = true;
}

visit(aQueue, visited, can1, matrix);

for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
visited[i][j] = false;

// push the right and bottom boundary
for (int i=0; i<m; ++i) {
can2[i][n-1] = true;
visited[i][n-1] = true;
aQueue.push(Cell(i, n-1, matrix[i][n-1]));
}

for (int i=0; i<n-1; ++i) {
can2[m-1][i] = true;
visited[m-1][i] = true;
aQueue.push(Cell(m-1, i, matrix[m-1][i]));
}

visit(aQueue, visited, can2, matrix);

vector<pair<int, int>> res;
for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
if (can1[i][j] && can2[i][j])
res.push_back({i, j});

return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.