Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.
Example
Given 5*4 matrix
[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14.
struct MyPoint{
int x, y, h;
MyPoint(int xx, int yy, int hh):x(xx), y(yy), h(hh){}
};
struct Cmp{
bool operator()(const MyPoint &p1, const MyPoint &p2){
return p1.h > p2.h;
}
};
class Solution {
public:
/**
* @param heights: a matrix of integers
* @return: an integer
*/
int trapRainWater(vector<vector<int> > &heights) {
int m = heights.size();
if(m < ) return ;
int n = heights[].size();
if(n < ) return ;
int waterNum = ;
vector<vector<bool> > visit(m, vector<bool>(n, false));
priority_queue<MyPoint, vector<MyPoint>, Cmp> MyPointQue;
for(int i = ;i < n;++i){
MyPointQue.push(MyPoint(, i, heights[][i]));
MyPointQue.push(MyPoint(m - , i, heights[m - ][i]));
visit[][i] = true;
visit[m - ][i] = true;
}
for(int j = ;j < m - ;++j){
MyPointQue.push(MyPoint(j, , heights[j][]));
MyPointQue.push(MyPoint(j, n - , heights[j][n - ]));
visit[j][] = true;
visit[j][n - ] = true;
}
const int detX[] = {, , , -}, detY[] = {, -, , };
while(MyPointQue.size() > ){
MyPoint p = MyPointQue.top();
MyPointQue.pop();
for(int i = ;i < ;++i){
int xx = p.x + detX[i], yy = p.y + detY[i];
if(xx < || xx >= m || yy < || yy >= n) continue;
if(visit[xx][yy]) continue;
else{
int h = heights[xx][yy];
if(heights[xx][yy] < p.h){
h = p.h;
waterNum += p.h - heights[xx][yy];
}
MyPointQue.push(MyPoint(xx, yy, h));
visit[xx][yy] = true;
}
}
}
return waterNum;
}
};