<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>

#define pii pair<int, int>
#define piii pair<int, pii>
#define f first
#define s second

class Solution {
public:
    int m,n;
    bool isValid(int x, int y){
        return min(x,y) >= 0 && x < m && y < n;
    }

    int trapRainWater(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();

        vector<vector<bool>> visited(m+1, vector<bool>(n+1, false));
        priority_queue<piii, vector<piii>, greater<piii>> pq;
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};

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

        int ans = 0;
        while(!pq.empty()){
            int i = pq.top().s.f;
            int j = pq.top().s.s;
            int h = pq.top().f;
            pq.pop();

            if (visited[i][j]) continue;
            visited[i][j] = 1;
            ans += h - matrix[i][j];

            for (int k = 0; k < 4; k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (isValid(nx, ny) && !visited[nx][ny]){
                    pq.push({max(h, matrix[nx][ny]), {nx, ny}});
                }
            }
        }

        return ans;
    }
};
17943