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

import heapq

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        n = len(heightMap)
        m = len(heightMap[0])
        pq = []
        visited = set()
        for i in range(n):
            visited.add((i,0))
            heapq.heappush(pq, (heightMap[i][0], (i,0)))
            visited.add((i, m - 1))
            heapq.heappush(pq, (heightMap[i][m - 1], (i, m - 1)))
        for j in range(1, m - 1):
            visited.add((0,j))
            heapq.heappush(pq, (heightMap[0][j], (0,j)))
            visited.add((n - 1, j))
            heapq.heappush(pq, (heightMap[n - 1][j], (n - 1, j)))

        print(visited)

        ans = 0
        while pq:
            popped = heapq.heappop(pq)
            height = popped[0]
            x, y = popped[1]
            for x_delt, y_delt in [(1,0),(-1,0),(0,1),(0,-1)]:
                    x_d = x + x_delt
                    y_d = y + y_delt
                    # print(f"x_d={x_d},y_d={y_d},n={n},m={m},zefuck={x_d < n and y_d < m}")
                    if x_d >= 0 and x_d < len(heightMap) and y_d >= 0 and y_d < len(heightMap[0]) and not (x_d,y_d) in visited:
                        # if heightMap[x_d][y_d] < height:
                        if heightMap[x_d][y_d] < height:
                            ans += height - heightMap[x_d][y_d]
                        visited.add((x_d,y_d))
                        heapq.heappush(pq, (max(height, heightMap[x_d][y_d]), (x_d,y_d)))
        return ans


       
    def bfs(self, heightMap, i, j) -> int:
        n = len(heightMap)
        m = len(heightMap[0])
        visited = set([(i,j)])
        q = [((i, j), heightMap[i][j])]
        min_edge = sys.maxsize
        mins_max = heightMap[i][j]
        while q:
            layer = q
            print(f"layer={layer}")
            q = []
            temp_q = {}
            vals = []
            for cell in layer:
                x, y = cell[0]
                prev_highest = cell[1]
                # print(f"x={x},y={y},height[x][y]={ heightMap[x][y]},prev_highest={prev_highest}")
                # if heightMap[x][y] >= prev_highest:
                vals.append(prev_highest)
                if (x in [0, n - 1] or y in [0, m - 1]):
                    if prev_highest <= heightMap[i][j]:
                        return 0
                    min_edge = min(min_edge, prev_highest)
                for x_delt, y_delt in [(1,0),(-1,0),(0,1),(0,-1)]:
                    x_d = x + x_delt
                    y_d = y + y_delt
                    # print(f"x_d={x_d},y_d={y_d},n={n},m={m},zefuck={x_d < n and y_d < m}")
                    if x_d >= 0 and x_d < n and y_d >= 0 and y_d < m:
                        if (x in [0, n - 1] or y in [0, m - 1]):
                            ph = prev_highest
                        else:
                            ph = max(prev_highest, heightMap[x_d][y_d])
                        if not (x_d, y_d) in visited or ((x_d, y_d) in temp_q and ph < temp_q[(x_d, y_d)]):
                            # print(f"deltas appended (x_d,y_d)={(x_d,y_d)}, ph={ph}")
                            # new_height = max(heightMap[x][y], prev_highest)
                            visited.add((x_d,y_d))
                            temp_q[(x_d,y_d)] = ph
            # print(f"q after={q}")
            # vals = list(filter(lambda x: x > mins_max, vals))
            q = list(temp_q.items())
            print(f"appended={q}")
            min_val = min(vals) if vals else -1
            mins_max = max(mins_max, min_val)
            print(f"vals={vals},mins_max={mins_max}")
        # print("##############################")
        return max(min(mins_max, min_edge) - heightMap[i][j], 0)





22900