Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Example:
Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
After the rain, water is trapped between the blocks. The total volume of water trapped is 4.
Constraints:
1 <= m, n <= 110
0 <= heightMap[i][j] <= 20000
Solution
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
int row = heightMap.size(), col = heightMap[0].size();
vector<vector<bool>> visited(row, vector<bool>(col, false));
int minimum = INT_MAX;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (!(i==0 || i==row-1 || j==0 || j==col-1)) continue;
que.push({heightMap[i][j], i * col + j});
visited[i][j] = true;
minimum = min(minimum, heightMap[i][j]);
}
}
pair<int, int> dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int ans = 0;
while (!que.empty()) {
pair<int, int> val = que.top();
que.pop();
int height = val.first;
int x = val.second / col;
int y = val.second % col;
minimum = max(minimum, height);
for (const pair<int, int>& d: dir) {
int nx = x + d.first;
int ny = y + d.second;
if (nx >= row || nx < 0 || ny < 0 || ny >= col || visited[nx][ny]) continue;
visited[nx][ny] = true;
if (heightMap[nx][ny] < minimum) {
ans += minimum - heightMap[nx][ny];
}
que.push({heightMap[nx][ny], nx * col + ny});
}
}
return ans;
}
};
