class Solution {
public:
    int n, m;
    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};
    int trapRainWater(vector<vector<int>>& heightMap) {
        n = heightMap.size(), m = heightMap[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        priority_queue<Cell> pq;

        for (int j = 0; j < m; j++) {
            pq.push(Cell(heightMap[0][j], 0, j));
            visited[0][j] = true;

            pq.push(Cell(heightMap[n-1][j], n-1, j));
            visited[n-1][j] = true;
        }
        for (int i = 1; i < n - 1; i++) {
            pq.push(Cell(heightMap[i][0], i, 0));
            visited[i][0] = true;

            pq.push(Cell(heightMap[i][m-1], i, m-1));
            visited[i][m-1] = true;
        }

        int totWater = 0;
        while(!pq.empty()) {
            Cell curr = pq.top(); pq.pop();
            int x = curr.x, y = curr.y, h = curr.height;
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visited[nx][ny]) continue;

                int nh = heightMap[nx][ny];
                if (h > nh) totWater += h - nh;

                pq.push(Cell(max(h, nh), nx, ny));
                visited[nx][ny] = true;
            }
        }
        return totWater;
    }

private:
    class Cell {
        public:
        int height;
        int x;
        int y;

        Cell(int _h, int _x, int _y) : height(_h), x(_x), y(_y){}
        bool operator < (const Cell& other) const {
            return height >= other.height;
        }
    };
};