class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        int ans = 0;
        vector<vector<int>> seen (m, vector<int>(n, 0));
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

        for (int i = 0; i < m; ++i) {
            if (i == 0 || i == m-1) {
                for (int j = 0; j < n; ++j) {
                    pq.push({heightMap[i][j], {i, j}});
                    seen[i][j] = 1;
                }
            } else {
                pq.push({heightMap[i][0], {i, 0}});
                seen[i][0] = 1;
                pq.push({heightMap[i][n-1], {i, n-1}});
                seen[i][n-1] = 1;
            }
        }

        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            for (int i = 0; i < 4; ++i) {
                int newI = top.second.first + direction[i][0];
                int newJ = top.second.second + direction[i][1];
                if (newI >= 0 && newI < m && newJ >= 0 && newJ < n && seen[newI][newJ] == 0) {
                    ans += max(0, top.first - heightMap[newI][newJ]);
                    heightMap[newI][newJ] = max(top.first, heightMap[newI][newJ]);
                    pq.push({heightMap[newI][newJ], {newI, newJ}});
                    seen[newI][newJ] = 1;
                }
            }
        }

        return ans;
    }
private:
    vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
};