407. Trapping Rain Water II
利用外围边界，依次朝里面找，只是新加入heap的值需要取其原来值和新值比较高的那个点作为高度。
class Solution(object):
def trapRainWater(self, heightMap):
"""
:type heightMap: List[List[int]]
:rtype: int
"""
if not heightMap:
return 0
# 利用heap来做
visited = [[False for _ in range(len(heightMap[0]))] for _ in range(len(heightMap))]
# init
heap = []
for i in range(len(heightMap)):
for j in range(len(heightMap[0])):
if i == 0 or i == len(heightMap) - 1 or j == 0 or j == len(heightMap[0]) - 1:
heapq.heappush(heap, [heightMap[i][j], i, j])
visited[i][j] = True
# find the lowest one
res = 0
while heap:
cur, i, j = heapq.heappop(heap)
for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
if 0 <= x < len(heightMap) and 0 <= y < len(heightMap[0]) and not visited[x][y]:
res += max(0, cur - heightMap[x][y])
heapq.heappush(heap, [max(cur, heightMap[x][y]), x, y])
visited[x][y] = True
return res
