# 12-liner C++ concise priority queue with global indexing, no self-defined struct (with explanation and comments)

• As many fellow coders have posted here, the key to solve this problem is to start from boundary cells, look for lowest ones first, and BSF to search neighbors. Searching in this order is because we can only decide the trapped water height at boundary cells with lowest height first.

No self-made struct is needed because C++ STL has provided enough container templates for manipulation to get what we want.

Some key variables and treatment in my code below:

1. A priority queue `q` of type `priority_queue<pair<int, int>,vector<pair<int, int>>,greater<pair<int, int>>>` is used to store currently searched pairs `(h, i)` with lowest `h` as priority, where `i` is the global index of a cell.
2. Global index `i` of a cell at location `(row, col)` can be easily converted to local index:
• `row = i/n, col = i%n`, where `n` is number of columns in the given height map `h[][]`.
3. `maxh` is the maximum height so far in BSF process. This variables is used to determined the height of water trapped at each current cell.
``````    typedef pair<int, int> PI;
int trapRainWater(vector<vector<int>>& h) {
int m, n, water = 0;
if(!(m=h.size()) || !(n=h[0].size())) return 0; // check map bounds

vector<int> visited(m*n,0); // if cell(i) is visited
priority_queue<PI,vector<PI>,greater<PI>> q; // priority queue of (h,index) by min height

for (int i = 0; i < m*n; ++i) // initialize queue with all boundary cells
if (i%n*((i+1)%n)*(i/n)*(i/n-m+1)==0) q.emplace(h[i/n][i%n],i), visited[i] = 1;

for(int i, maxh = INT_MIN; q.size(); ) { // BSF
auto cur = q.top(); q.pop(); maxh = max(maxh, cur.first);
for(int d : {n, -n, 1, -1})
if((i = cur.second+d)>=0 && i<m*n && !visited[i]) // a valid unvisited neighbor
water += max(maxh-h[i/n][i%n], 0), q.emplace(h[i/n][i%n], i), visited[i] = 1;
}
return water;
}
``````

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