def trapRainWater(self, heights):
        m = len(heights)
        n = len(heights[0])

        visited = [[False for _ in xrange(n)] for _ in xrange(m)]

        # add cells at the four edges
        for i in xrange(m):
            heapq.heappush(self.h, Cell(i, 0, heights[i][0]))
            heapq.heappush(self.h, Cell(i, n-1, heights[i][n-1]))

        for j in xrange(1, n-1):
            heapq.heappush(self.h, Cell(0, j, heights[0][j]))
            heapq.heappush(self.h, Cell(m-1, j, heights[m-1][j]))

        # BFS with heap
        while self.h:
            cur = heapq.heappop(self.h)
            visited[cur.i][cur.j] = True
            for dir in self.dirs:
                next_i = cur.i+dir[0]
                next_j = cur.j+dir[1]
                if 0 <= next_i < m and 0 <= next_j < n:
                    nex = Cell(next_i, next_j, heights[next_i][next_j])
                    if not visited[nex.i][nex.j]:
                        visited[nex.i][nex.j] = True  # additional, to avoid TLE
                        if nex.h < cur.h:  # fill
                            self.trapped += cur.h-nex.h
                            nex.h = cur.h
                        heapq.heappush(self.h, nex)

        return self.trapped
Find the min height with no water that higher than the current height and keep it.
dataset/ETHPy150Open algorhythms/LintCode/Trapping Rain Water II.py/Solution.trapRainWater