C++ 的接雨水问题及题解分析

题目

给定一个m x n的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

说明:

m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。

示例：

如上图所示，这是下雨前的高度图[[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,vector<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;
    }
};