C++ Solution using Heap


  • 0
    Y
    class Solution {
    struct point{
        int height, level, x, y;
        
        point(){}
        
        point (int h, int l, int v_x, int v_y){
            height = h, level = l, x = v_x, y = v_y;
        }
        
        bool operator < (const point &a)const{
            return a.level < level;
        }
    };
    public:
        int trapRainWater(vector<vector<int>>& heightMap) {
            int sum = 0;
            if(heightMap.size() == 0 || heightMap[0].size() == 0)
                return sum;
            int n = heightMap.size(), m = heightMap[0].size(), new_level = 0, old_level = 0, v_x = 0, v_y = 0;
            priority_queue<point> pq;
            vector<vector<point>> mp(n, vector<point>(m));
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m; ++ j){
                    if(i == 0 || i == n - 1 || j == 0 || j == m - 1){
                        point pnt(heightMap[i][j], heightMap[i][j], i, j);
                        pq.push(pnt);
                        mp[i][j] = pnt;
                    }else{
                        point pnt(heightMap[i][j], INT_MAX, i, j);
                        mp[i][j] = pnt;
                    }
                }
            }
            
            point u, v;
            while(!pq.empty()){
                u = pq.top();
                pq.pop();
                //printf("u_level = %d\n",u.level);
                for(int i = 0; i < 4; ++ i){
                    v_x = u.x + dir[i][0], v_y = u.y + dir[i][1];
                    if(v_x >= 0 && v_x < n && v_y >= 0 && v_y < m){
                        v.height = mp[v_x][v_y].height;
                        old_level = mp[v_x][v_y].level;
                        new_level = max(v.height, min(mp[v_x][v_y].level, u.level));
                        if(new_level != old_level){
                  //          v.level = new_level;
                 //           printf("x = %d,y = %d,v_level = %d\n",v.x,v.y,v.level);
                            mp[v_x][v_y].level = new_level;
                            pq.push(mp[v_x][v_y]);
                        }
                    }
                }
            }
            
            for(int i = 1; i < n - 1; ++ i){
                for(int j = 1; j < m - 1; ++ j){
            //        printf("%d %d\n",mp[i][j].level, mp[i][j].height);
                    sum += (mp[i][j].level - mp[i][j].height);
                }
            }
            return sum;
        }
    private:
        int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    };
    

Log in to reply
 

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