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

class Solution {
private:
    vector<int> dx={0,0,1,-1};
    vector<int> dy={1,-1,0,0};
    bool isValid(int x, int y, int n, int m){
        return (x>=0) && (y>=0) && (x<n)  && (y<m);
    }
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        set<pair<int,pair<int,int>>> st;
        int n = heightMap.size();
        int m = heightMap[0].size();
        vector<vector<int>> vis(n,vector<int> (m,0));
        for(int i=0;i<m;i++){
            st.insert({heightMap[0][i],{0,i}});
            st.insert({heightMap[n-1][i],{n-1,i}});
            vis[0][i]=1;
            vis[n-1][i]=1;
        }
        for(int i=0;i<n;i++){
            st.insert({heightMap[i][0],{i,0}});
            st.insert({heightMap[i][m-1],{i,m-1}});
            vis[i][0]=1;
            vis[i][m-1]=1;
        }
        int ans=0;
        while(!st.empty()){
            auto it = st.begin();
            int mini =(*it).first;
            while(!st.empty()){
                auto it = st.begin();
                int cur = (*it).first;
                if(cur>mini) break;
                ans+=(mini-cur);
                int x = (*it).second.first;
                int y=(*it).second.second;
                st.erase(it);
                for(int i=0;i<4;i++){
                    int xx = x+dx[i];
                    int yy=y+dy[i];
                    if(!isValid(xx,yy,n,m)) continue;
                    if(vis[xx][yy]) continue;
                    st.insert({heightMap[xx][yy],{xx,yy}});
                    vis[xx][yy]=1;
                }
            }
        }
        return ans;
    }
};
25756