title
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
示例 1:
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
示例 2:
输入: 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]]
输出: 10
提示:
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104
solution
Dijkstra. 从外向内扩展，路径定义为water高度。
class Directions:
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
diagonal_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
all_dirs = dirs + diagonal_dirs
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m, n = len(heightMap), len(heightMap[0])
h = []
import heapq
dist = {}
for i in range(m):
heapq.heappush(h, (heightMap[i][0], i, 0))
heapq.heappush(h, (heightMap[i][n - 1], i, n - 1))
for j in range(1, n - 1):
heapq.heappush(h, (heightMap[0][j], 0, j))
heapq.heappush(h, (heightMap[m - 1][j], m - 1, j))
ans = 0
while h:
ph, x, y = heapq.heappop(h)
if (x, y) in dist: continue
dist[(x, y)] = max(heightMap[x][y], ph)
if ph > heightMap[x][y]:
ans += ph - heightMap[x][y]
for dx, dy in Directions.dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in dist:
heapq.heappush(h, (dist[(x, y)], nx, ny))
# print(dist)
return ans