Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.
![](https://images2015.cnblogs.com/blog/606555/201607/606555-20160706165941233-1814785545.jpg)
这是一道非常有意思的题目。如果明白了灌水类问题的核心思之后则可以明白,当前位置可灌的水为周围最低的bar(包括灌完水的)决定的.每次用堆找到一个最低的bar(弹出这个最低的bar,意思是处理过)之后该bar周围找点,如果没有加入过堆,且值小于堆顶值,则进行灌水.代码如下:
class Solution:
# @param heights: a matrix of integers
# @return: an integer
def trapRainWater(self, heights):
if not heights or not heights[0]:
return 0
import heapq
heap = []
m = len(heights)
n = len(heights[0])
visited = [[False] * n for i in xrange(m)]
for i in xrange(n):
visited[0][i] = True
heapq.heappush(heap, (heights[0][i],(0,i)))
if m > 1:
visited[-1][i] = True
heapq.heappush(heap, (heights[-1][i],(m-1,i)))
for j in xrange(m):
visited[j][0] = True
heapq.heappush(heap, (heights[j][0], (j,0)))
if n > 1:
visited[j][-1] = True
heapq.heappush(heap, (heights[j][-1], (j, n-1)))
area = 0
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
while heap:
cur = heapq.heappop(heap)
for i in xrange(4):
x = cur[1][0] + dx[i]
y = cur[1][1] + dy[i]
if x >= 0 and y>= 0 and x < m and y < n and not visited[x][y]:
visited[x][y] = True
if heights[x][y] < cur[0]:
area += cur[0] - heights[x][y]
heapq.heappush(heap, (cur[0],(x,y)))
else:
heapq.heappush(heap, (heights[x][y],(x,y)))
return area
注意不用担心斜对角线漏水~
转载于:https://www.cnblogs.com/sherylwang/p/5647474.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)