<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 {
public:
    bool check(int a , int b , int n ,int m){
        return (a>=0 && b>=0 && a<n && b<m);
    }
    vector<pair<int,int>>movement = {{1,0} , {-1,0} , {0,1} , {0,-1}};

    int trapRainWater(vector<vector<int>>& height) {
            int n = height.size();
            int m = height[0].size();
            vector<vector<int>>vis(n , vector<int>(m,0));
            multiset<pair<int,pair<int,int>>>ms;

            for(int i = 0;i<n;i+=1){
                for(int j = 0;j<m;j+=1){
                    if(i == 0 || j == 0 || i == n-1 || j == m-1){
                        ms.insert({height[i][j] , {i,j}});
                        vis[i][j] = 1;
                    }
                }
            }

            int ans = 0;
            while(ms.size()){
                auto it = *ms.begin();
                ms.erase(ms.begin());
                int ht = it.first;
                int i = it.second.first;
                int j = it.second.second;

                for(auto dir:movement){
                    int ii = i + dir.first;
                    int jj = j + dir.second;
                    if(check(ii,jj,n,m) && vis[ii][jj] == 0){
                        vis[ii][jj] = 1;
                        ans += max(0 , ht - height[ii][jj]);
                        ms.insert({max(ht , height[ii][jj]) , {ii,jj}});
                    }
                }
            }
            return ans;
        
    }
};
/*


*/
25443