407

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int rows = heightMap.size(), cols=heightMap[0].size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<bool> vis(rows*cols, false);

        for(int i=0; i<cols; i++){
            pq.push({heightMap[0][i], i});
            vis[i] = true;
            if(rows>1){
                pq.push({heightMap[rows-1][i], cols*(rows-1)+i});
                vis[cols*(rows-1)+i] = true;
            }
        }
        for(int i=0; i<rows; i++){
            pq.push({heightMap[i][0], cols*i});
            vis[cols*i] = true;
            if(cols>1){
                pq.push({heightMap[i][cols-1], cols*i+cols-1});
                vis[cols*i+cols-1] = true;
            }
        }

        int ans = 0;
        int curMax = 0;
        int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while(!pq.empty()){
            auto p = pq.top(); pq.pop();
            int curX = p.second/cols, curY = p.second%cols;
            curMax = max(curMax, p.first);
            for(int i=0; i<4; i++){
                int nextX = curX+dir[i][0], nextY = curY+dir[i][1];
                if(nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols || vis[nextX*cols+nextY]) continue;
                ans += (heightMap[nextX][nextY] < curMax) ? (curMax-heightMap[nextX][nextY]) : 0;
                pq.push({heightMap[nextX][nextY], nextX*cols+nextY});
                vis[nextX*cols+nextY] = true;
            }
        }
        return ans;
    }
};