priority_queue and unordered_set


  • 0
    L
    class Solution {
    public:
        class Unit{
            public:
            int i,j,h;
            Unit(int i,int j,int h){
                this->i=i;
                this->j=j;
                this->h=h;
            }
            bool operator<(const Unit &e)const{
                return this->h>e.h;
            }
        };
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        int trapRainWater(vector<vector<int>>& heightMap) {
            int res=0;
            int m=heightMap.size();
            if(m<=2){
                return res;
            }
            int n=heightMap[1].size();
            if(n<=2){
                return res;
            }
            priority_queue<Unit> q;
            unordered_set<int> set;
            for(int i=0;i<m;i++){
                q.push(Unit(i,0,heightMap[i][0]));
                set.insert(i*n);
                q.push(Unit(i,n-1,heightMap[i][n-1]));
                set.insert(i*n+n-1);
            }
            for(int i=1;i<n-1;i++){
                q.push(Unit(0,i,heightMap[0][i]));
                set.insert(i);
                q.push(Unit(m-1,i,heightMap[m-1][i]));
                set.insert((m-1)*n+i);
            }
            while(!q.empty()){
                Unit u=q.top();
                q.pop();
                for(int k=0;k<4;k++){
                    int row=u.i+dx[k];
                    int col=u.j+dy[k];
                    if(row>=0 && row<m && col>=0 && col <n && set.find(row*n+col)==set.end()){
                        if(heightMap[row][col]<u.h){
                            res+=u.h-heightMap[row][col];
                            heightMap[row][col]=u.h;
                        }
                        q.push(Unit(row,col,heightMap[row][col]));
                        set.insert(row*n+col);
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.