给定一个m x n的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
说明:
m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。
示例：
给出如下 3x6 的高度图:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
返回 4。
详见：https://leetcode.com/problems/trapping-rain-water-ii/description/
C++：
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if (heightMap.empty())
{
return 0;
}
int m = heightMap.size(), n = heightMap[0].size(), res = 0, mx = INT_MIN;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
{
q.push({heightMap[i][j], i * n + j});
visited[i][j] = true;
}
}
}
while (!q.empty())
{
auto t = q.top(); q.pop();
int h = t.first, r = t.second / n, c = t.second % n;
mx = max(mx, h);
for (int i = 0; i < dir.size(); ++i)
{
int x = r + dir[i][0], y = c + dir[i][1];
if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y])
{
continue;
}
visited[x][y] = true;
if (heightMap[x][y] < mx)
{
res += mx - heightMap[x][y];
}
q.push({heightMap[x][y], x * n + y});
}
}
return res;
}
};
参考：https://www.cnblogs.com/grandyang/p/5928987.html