<p>Given an <code>m x n</code> integer matrix <code>heightMap</code> representing the height of each unit cell in a 2D elevation map, return <em>the volume of water it can trap after raining</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/trap1-3d.jpg" style="width: 361px; height: 321px;" />
<pre>
<strong>Input:</strong> heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/trap2-3d.jpg" style="width: 401px; height: 321px;" />
<pre>
<strong>Input:</strong> heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
<strong>Output:</strong> 10
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == heightMap.length</code></li>
	<li><code>n == heightMap[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= heightMap[i][j] &lt;= 2 * 10<sup>4</sup></code></li>
</ul>

/*
the good point to start is at the edges of the matrix
and the water can flow out of the matrix from the edge only,
other inside cells will not lead the water to go out.

1. So insert all the edge ndoe heights in the PQ.
2. then we can pick the smallest edge node and check with nbrs how much water
they can keep in themselves
3. keep on doing this.
4. for nbr height greater we can't keep any water
5. for nbr height lesser only we can keep water for all other cases it will
overflow
*/

class Solution {

    class Pair {
    public:
        int x, y, height;
        Pair(int height, int x, int y) : height(height), x(x), y(y) {}
    };

    int dir[4][4] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    struct ComparePairs {
        bool operator()(const Pair* p1, const Pair* p2) {
            return p1->height > p2->height; // Min-heap based on the second element
            }
    };
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int n = heightMap.size(), m = heightMap[0].size();
        priority_queue<Pair*, vector<Pair*>, ComparePairs> pq;
        vector<vector<int>> visited(n, vector<int>(m, false));
        int ans = 0;

        // Traverse through the edges and add all the nodes in the PQ with there
        //     height
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1 && !visited[i][j]) {
                    Pair* p = new Pair(heightMap[i][j], i, j);
                    pq.push(p);
                    visited[i][j] = true;
                }
            }
        }

        // Do a bfs
        // Pop the element
        // for all the nrbs if the its not visited
        // Mark as visited
        // the selected node height is greater than the nbr height
        // we can fill the water in the nbr node by height_node - height_nbr
        // then make the height of the nbr as the current node height
        // push the nbr node with the height with the node height
        // the selected node height is equal than the nbr height
        // then push the node in pq with the node height
        // the selected node height is lesser than the nbr height
        // then we can’t fill any water in the current place/
        // we will push the current node in pq with it’s current height
        while (!pq.empty()) {
            Pair* p = pq.top();
            cout << p->x << " " << p->y << " " << p->height << endl; 
            pq.pop();
            for (int i = 0; i < 4; i++) {
                int newX = p->x + dir[i][0];
                int newY = p->y + dir[i][1];
                // cout << newX << " " << newY << endl;

                if (newX >= 0 && newX < n && newY >= 0 && newY < m &&
                    !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    ans += max(0, p->height - heightMap[newX][newY]);
                    if (heightMap[newX][newY] <= p->height) {
                        pq.push(new Pair(p->height, newX, newY));
                    } else {
                        pq.push(new Pair(heightMap[newX][newY], newX, newY));
                    }
                }
            }
        }

        return ans;
    }
};

22006