C++ Floodfill solution with priority_queue

• ``````class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int n = heightMap.size();
if(n == 0) return 0;
int m = heightMap[0].size();
if(m == 0) return 0;
int result = 0;
vector<vector<bool>> isVisit(n, vector<bool>(m, false));
priority_queue<pair<int, pair<int, int>>> myQueue;

for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(i==0 || i == n-1 || j == 0 || j == m-1) {
// we push all the boundary points into the priorrity_queue
isVisit[i][j] = true;
// push negative height as the priority_queue is a big heap
myQueue.push(make_pair(-heightMap[i][j], make_pair(i, j)));
}
}
}
const int go_x[4] = {1, -1, 0, 0};
const int go_y[4] = {0, 0, 1, -1};
while(!myQueue.empty()) {
// We always extract the smallest block and try to extend it to its four neighbors.
auto temp_front = myQueue.top();
myQueue.pop();
int temp_height = -temp_front.first;
int fx = temp_front.second.first;
int fy = temp_front.second.second;
for(int d = 0; d < 4; d++) {
int tx = fx + go_x[d];
int ty = fy + go_y[d];
if(tx < 0 || tx >=n || ty < 0 || ty >= m || isVisit[tx][ty]) continue;
if(heightMap[tx][ty] < temp_height) {
// if its neightbour's height is smallest than it, we fill water in it.
result += (temp_height - heightMap[tx][ty]);
heightMap[tx][ty] = temp_height;
}
isVisit[tx][ty] = true;
myQueue.push(make_pair(-heightMap[tx][ty], make_pair(tx, ty)));
}
}
return result;
}
};
``````

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