给定一个 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。
struct Node{
int i,j,h;
Node(int ii,int jj,int hh):i(ii),j(jj),h(hh){}
bool operator <(const Node &root) const{
return h>root.h;
}
};
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if(heightMap.size()==0) return 0;
int m=heightMap.size(),n=heightMap[0].size(),area=0,h=0;
priority_queue<Node> q;
vector<vector<bool>> visit(m,vector<bool>(n,false));
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(Node(i,j,heightMap[i][j]));
visit[i][j]=true;
}
}
}
vector<int> x={0,0,-1,1},y={-1,1,0,0};
while(!q.empty())
{
auto f=q.top();
if(h<f.h) h++;
else
{
q.pop();
for(int k=0;k<4;k++)
{
int i=f.i+x[k],j=f.j+y[k];
if(i>=0&&i<m&&j>=0&&j<n&&visit[i][j]==false)
{
int hh=heightMap[i][j];
if(hh<h) area+=h-hh;
q.push(Node(i,j,hh));
visit[i][j]=true;
}
}
}
}
return area;
}
};
此题用BFS来做。创建一个优先级队列，该队列中是将高度小的放在队首。先将四周一圈的格子加入队列中，并将这些格子的状态设为已访问过。下面开始BFS，从队列的头部取出元素，并用其高度更新海平面level，然后从该格子向四周寻找格子，如果某格子未被访问过，那么将其状态设为已访问过，然后判断如果其高度小于海平面，那么把它们的高度差加到ans中，否则不操作。接下来将该格子加入到优先级队列中。如此进行，当优先级队列为空时退出循环，返回ans。
https://www.cnblogs.com/grandyang/p/5928987.html
这道题是之前那道 Trapping Rain Water 的拓展，由 2D 变 3D 了，感觉很叼。但其实解法跟之前的完全不同了，之前那道题由于是二维的，我们可以用双指针来做，而这道三维的，我们需要用 BFS 来做，解法思路很巧妙，下面我们就以题目中的例子来进行分析讲解，多图预警，手机流量党慎入：
首先我们应该能分析出，能装水的底面肯定不能在边界上，因为边界上的点无法封闭，那么所有边界上的点都可以加入 queue，当作 BFS 的启动点，同时我们需要一个二维数组来标记访问过的点，访问过的点我们用红色来表示，那么如下图所示：
我们再想想，怎么样可以成功的装进去水呢，是不是周围的高度都应该比当前的高度高，形成一个凹槽才能装水，而且装水量取决于周围最小的那个高度，有点像木桶原理的感觉，那么为了模拟这种方法，我们采用模拟海平面上升的方法来做，我们维护一个海平面高度 mx，初始化为最小值，从1开始往上升，那么我们 BFS 遍历的时候就需要从高度最小的格子开始遍历，那么我们的 queue 就不能使用普通队列了，而是使用优先级队列，将高度小的放在队首，最先取出，这样我们就可以遍历高度为1的三个格子，用绿色标记出来了，如下图所示：
如上图所示，向周围 BFS 搜索的条件是不能越界，且周围格子未被访问，那么可以看出上面的第一个和最后一个绿格子无法进一步搜索，只有第一行中间那个绿格子可以搜索，其周围有一个灰格子未被访问过，将其加入优先队列 queue 中，然后标记为红色，如下图所示：
那么优先队列 queue 中高度为1的格子遍历完了，此时海平面上升1，变为2，此时我们遍历优先队列 queue 中高度为2的格子，有3个，如下图绿色标记所示：
我们发现这三个绿格子周围的格子均已被访问过了，所以不做任何操作，海平面继续上升，变为3，遍历所有高度为3的格子，如下图绿色标记所示：
由于我们没有特别声明高度相同的格子在优先队列 queue 中的顺序，所以应该是随机的，其实谁先遍历到都一样，对结果没啥影响，我们就假设第一行的两个绿格子先遍历到，那么那么周围各有一个灰格子可以遍历，这两个灰格子比海平面低了，可以存水了，把存水量算出来加入结果 res 中，如下图所示：
上图中这两个遍历到的蓝格子会被加入优先队列 queue 中，由于它们的高度小，所以下一次从优先队列 queue 中取格子时，它们会被优先遍历到，那么左边的那个蓝格子进行BFS搜索，就会遍历到其左边的那个灰格子，由于其高度小于海平面，也可以存水，将存水量算出来加入结果 res 中，如下图所示：
等两个绿格子遍历结束了，它们会被标记为红色，蓝格子遍历会先被标记红色，然后加入优先队列 queue 中，由于其周围格子全变成红色了，所有不会有任何操作，如下图所示：
此时所有的格子都标记为红色了，海平面继续上升，继续遍历完优先队列 queue 中的格子，不过已经不会对结果有任何影响了，因为所有的格子都已经访问过了，此时等循环结束后返回res即可