Description:
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.
Solution:
class Node {
public:
int x, y, h;
Node(int x, int y, int h): x(x), y(y), h(h) {}
};
bool operator>(const Node& n1, const Node& n2) {
return n1.h > n2.h;
}
class Solution {
public:
/**
* @param heights: a matrix of integers
* @return: an integer
*/
int trapRainWater(vector<vector<int> > &heights) {
auto m = (int)heights.size();
if (m < 3) return 0;
auto n = (int)heights[0].size();
if (n < 3) return 0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
priority_queue<Node, vector<Node>, ::greater<Node>> heap;
for (int i = 0; i < m; ++i) {
heap.push(Node(i, 0, heights[i][0]));
visited[i][0] = true;
heap.push(Node(i, n-1, heights[i][n-1]));
visited[i][n-1] = true;
}
for (int i = 1; i < n-1; ++i) {
heap.push(Node(0, i, heights[0][i]));
visited[0][i] = true;
heap.push(Node(m-1, i, heights[m-1][i]));
visited[m-1][i] = true;
}
int rc = 0;
while (!heap.empty()) {
auto node = heap.top();
heap.pop();
int x = node.x, y = node.y, h = node.h;
if (x >= 1 && !visited[x-1][y]) {
if (heights[x-1][y] < h)
rc += h - heights[x-1][y];
heap.push(Node(x-1, y, max(h, heights[x-1][y])));
visited[x-1][y] = true;
}
if (x <= m-2 && !visited[x+1][y]) {
if (heights[x+1][y] < h)
rc += h - heights[x+1][y];
heap.push(Node(x+1, y, max(h, heights[x+1][y])));
visited[x+1][y] = true;
}
if (y >= 1 && !visited[x][y-1]) {
if (heights[x][y-1] < h)
rc += h - heights[x][y-1];
heap.push(Node(x, y-1, max(h, heights[x][y-1])));
visited[x][y-1] = true;
}
if (y <= n-2 && !visited[x][y+1]) {
if (heights[x][y+1] < h)
rc += h - heights[x][y+1];
heap.push(Node(x, y+1, max(h, heights[x][y+1])));
visited[x][y+1] = true;
}
}
return rc;
}
};
转载于:https://www.cnblogs.com/deofly/p/trapping-rain-water-ii.html
