Trapping Rain Water II

这道题总的概念就是把第一问的双指针算法从一维提升到了二维，实际上还是从边界逐渐缩小范围往中心逼近的做法，在二维的数据上就更像围猎那种感觉，通过一直弹出最小板往内部寻找可以灌水的坑，跟第一问一样，我们还是得在找到可以灌水的坑后把它填到当前最低板的高度再放进堆，一道非常有意思的问题

class Solution(object):
    def trapRainWater(self, heightMap):
        n = len(heightMap)
        if not n:
            return 0

        m = len(heightMap[0])
        if not m:
            return 0

        heap = []
        checker = set()
        for i in xrange(2):
            for j in xrange(m):
                heapq.heappush(heap, Point((n - i) % n, j, heightMap[(n - i) % n][j]))
                checker.add(((n - i) % n, j,))

        for i in xrange(2):
            for j in xrange(n):
                heapq.heappush(heap, Point(j, (m - i) % m, heightMap[j][(m - i) % m]))
                checker.add((j, (m - i) % m,))

        result = 0
        while heap:
            node = heapq.heappop(heap)
            for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                curRow, curCol = i + node.x, j + node.y
                if 0 <= curRow < n and 0 <= curCol < m:
                    if (curRow, curCol,) not in checker:
                        checker.add((curRow, curCol,))
                        if node.val > heightMap[curRow][curCol]:
                            result += (node.val - heightMap[curRow][curCol])
                        heapq.heappush(heap, Point(curRow, curCol, max(node.val, heightMap[curRow][curCol])))


        return result

class Point:
    def __init__(self, x, y, val):
        self.x = x
        self.y = y
        self.val = val

    def __cmp__(self, other):
        return cmp(self.val, other.val)