​LeetCode刷题实战407：接雨水 II

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;
    }
};