题目：
Given n * m non-negative integers representing an elevation map 2d where the area of each cell is 1 * 1, compute how much water it is able to trap after raining.
思路：
这道题是前面一道题的一个延伸，http://www.cnblogs.com/AndyJee/p/4821590.html
前面的给出是一维数组，而这里提供的是二维数组，形象地理解，就是提供了一个立体三维得柱形容器，求该容器所能容纳的最大体积。
由于水是往低处流的， 所以对于这一类trapping water问题，我们只用从最外层开始往内接雨水就可以。
首先从矩阵的最外层中找到最小的柱子，可以通过堆来实现，当堆不为空的情况下，每次弹出的都是高度最小的柱子，这时候从该柱子出发，遍历其周边的四个方向（BSF）的柱子，如果某个柱子未到达或超出边界且尚未被访问，则将该柱子加入堆中，如果该柱子的高度比当前柱子高度小，则更新该柱子的高度，同时记录此处所容纳的水，直至堆为空。
代码：
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<queue> using namespace std; struct cell{
int x;
int y;
int h;
cell(int xx,int yy,int hh):x(xx),y(yy),h(hh){};
bool operator<(const cell &c)const{
return h>c.h;
}
}; /*
bool operator<(const cell &a,const cell &b){
return a.h>b.h;
}
*/ int trapRainWater(const vector<vector<int> > &heights){
int m=heights.size();
int n=heights[].size();
vector<vector<int> > visited(m,vector<int>(n,)); int dx[]={,-,,};
int dy[]={,,,-}; priority_queue<cell> pq;
for(int i=;i<n;i++){
pq.push(cell(,i,heights[][i]));
pq.push(cell(m-,i,heights[m-][i]));
visited[][i]=;
visited[m-][i]=;
} for(int i=;i<m;i++){
pq.push(cell(i,,heights[i][]));
pq.push(cell(i,n-,heights[i][n-]));
visited[i][]=;
visited[i][n-]=;
} int ans=;
while(!pq.empty()){
cell c=pq.top();
pq.pop(); for(int i=;i<;i++){
for(int j=;j<;j++){
int nextx=c.x+dx[i];
int nexty=c.y+dy[i];
if(nextx>= && nextx<m && nexty>= && nexty<n && visited[nextx][nexty]==){
visited[nextx][nexty]=;
int h=max(c.h,heights[nextx][nexty]);
pq.push(cell(nextx,nexty,h));
ans+=max(,c.h-heights[nextx][nexty]);
}
}
}
}
return ans;
} int main(){
vector<vector<int> > heights={
{,,,},
{,,,},
{,,,},
{,,,},
{,,,}
}; cout << trapRainWater(heights) <<endl; // ans=14
return ;
}