# Not so short but easily understandable BSF priority queue C++ solution

• This problem is very similar to 2D Rain Trap Water. The ocean's boundary cells are added to priority queue first and then propagate to the neighboring cells of the top of queue. A struct "Height" is created to store x-y coordinates, height, flow accessible, visited flags. The comparator of priority queue is defined by the "greater" comparison of cell's height since the water can only flow from equal or higher elevation to lower one. I am only making the code readable and didn't optimize on space usage.

``````public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& a) {
vector<pair<int, int>> res;
m = a.size(); if (!m) return res;
n = a[0].size(); if (!n) return res;
cells.resize(m);
// create cells and initialize queues for pacific and atlantic
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
cells[i].emplace_back(i, j, a[i][j]);
if (i == 0 || j == 0) {
cells[i][j].flow |= 1; cells[i][j].visited |= 1;
pacific.push(cells[i][j]);
}
if (i == m - 1 || j == n - 1) {
cells[i][j].flow |= 1 << 1; cells[i][j].visited |= 1 << 1;
atlantic.push(cells[i][j]);
}
}
// set flow flags for both oceans
setFlow(0); setFlow(1);
// get locations accessible to both oceans
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (cells[i][j].flow == 3) res.emplace_back(i, j);
return res;
}

private:
// BSF: set flow and visited flags for an ocean
void setFlow(int isAtlantic) {
auto q = isAtlantic? atlantic : pacific;
while (!q.empty()) {
auto cur = q.top(); q.pop();
for (auto& d : dirs) {
int i = cur.x + d[0], j = cur.y + d[1];
if (i < 0 || i >= m || j < 0 || j >= n || (cells[i][j].visited&(1<< isAtlantic))) continue;
cells[i][j].visited |= (1 << isAtlantic);
if (cells[i][j].h >= cur.h) {
cells[i][j].flow |= 1 << isAtlantic; q.push(cells[i][j]);
}
}
}
}

struct Height {
int x, y, h;
int flow;    // 2-bit binary 00: low bit for Pacific, high bit for Atlantic
int visited; // 2-bit binary 00: low bit for Pacific, high bit for Atlantic
Height(int xx, int yy, int hh) :flow(0), visited(0), x(xx), y(yy), h(hh) {}
};

struct HComp {
bool operator()(Height a, Height b) { return a.h > b.h; }
};

int m, n; // grid dimensions
vector<vector<Height>> cells;
priority_queue<Height, vector<Height>, HComp> pacific, atlantic;
vector<vector<int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
``````

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