Givenn_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.
Have you met this question in a real interview?
Yes
Example
Given5*4matrix
[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return14.
class Solution {
public:
/\*\*
\* @param heights: a matrix of integers
\* @return: an integer
\*/
int trapRainWater\(vector<vector<int> > &heights\) {
// write your code here
if \(heights.empty\(\) \|\| heights\[0\].empty\(\)\) {
return 0;
}
int water = 0;
auto cmp = \[\]\(Cell left, Cell right\) { return left.h > right.h; };
priority\_queue<Cell, vector<Cell>, decltype\(cmp\)> q\(cmp\);
//priority\_queue<Cell> q;
int n = heights.size\(\);
int m = heights\[0\].size\(\);
//bool visited\[n\]\[m\] = {{0}};
vector<vector<bool>> visited\(n, vector<bool>\(m, false\)\);
for \(int i = 0; i < n; ++i\) {
q.emplace\(i, 0, heights\[i\]\[0\]\);
q.emplace\(i, m-1, heights\[i\]\[m-1\]\);
visited\[i\]\[0\] = true;
visited\[i\]\[m-1\] = true;
}
for \(int j = 1; j < m-1; ++j\) {
q.emplace\(0, j, heights\[0\]\[j\]\);
q.emplace\(n-1, j, heights\[n-1\]\[j\]\);
visited\[0\]\[j\] = true;
visited\[n-1\]\[j\] = true;
}
// int offsets\[4\]\[2\] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
vector<vector<int>> offsets = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while \(!q.empty\(\)\) {
auto cell = q.top\(\);
q.pop\(\);
for \(auto offset : offsets\) {
int i = cell.x + offset\[0\];
int j = cell.y + offset\[1\];
if \(isInsideArea\(i, j, n, m\) && !visited\[i\]\[j\]\) {
visited\[i\]\[j\] = true;
water += max\(cell.h - heights\[i\]\[j\], 0\);
q.emplace\(i, j, max\(cell.h, heights\[i\]\[j\]\)\);
}
}
}
return water;
}
private:
struct Cell {
Cell\(int x, int y, int h\) {
this->x = x;
this->y = y;
this->h = h;
}
bool operator< \(const Cell &rhs\) const{
return h > rhs.h;
}
int x, y, h;
};
bool isInsideArea\(int i, int j, int n, int m\) {
return i >=0 && i < n && j >= 0 && j < m;
}
};