题目链接：407. 接雨水 II
42. 接雨水已经很难了。。。这次又增加了难度。。。思路和一维的接雨水是一样的。
假定给定范围内的雨水已经接满：
- 首先，边界上肯定不会接到雨水，此时边界的高度即输入高度。
- 那么除边界外，每一个位置
i, j处的高度等于它四周高度的最小值。
使用优先队列，从最低的位置开始蓄水，直到蓄满给定范围。
import heapq
from typing import List
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m = len(heightMap)
if m <= 2:
return 0
n = len(heightMap[0])
if n <= 2:
return 0
q, visited = [], set()
for i in range(m):
heapq.heappush(q, (heightMap[i][0], i, 0))
heapq.heappush(q, (heightMap[i][n - 1], i, n - 1))
visited.add((i, 0))
visited.add((i, n - 1))
for j in range(n):
heapq.heappush(q, (heightMap[0][j], 0, j))
heapq.heappush(q, (heightMap[m - 1][j], m - 1, j))
visited.add((0, j))
visited.add((m - 1, j))
ans = 0
while len(q) > 0:
height, x, y = heapq.heappop(q)
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
i, j = x + dx, y + dy
if 0 <= i < m and 0 <= j < n and (i, j) not in visited:
visited.add((i, j))
h = max(height, heightMap[i][j])
ans += h - heightMap[i][j]
heapq.heappush(q, (h, i, j))
return ans