python solution with heap
\nclass Solution(object):\n    def trapRainWater(self, heightMap):\n        if not heightMap or not heightMap[0]:\n            return 0\n        \n        impor
```\nclass Solution(object):\n    def trapRainWater(self, heightMap):\n        if not heightMap or not heightMap[0]:\n            return 0\n        \n        import heapq    \n        m, n = len(heightMap), len(heightMap[0])\n        heap = []\n        visited = [[0]*n for _ in xrange(m)]\n\n        # Push all the block on the border into heap\n        for i in xrange(m):\n            for j in xrange(n):\n                if i == 0 or j == 0 or i == m-1 or j == n-1:\n                    heapq.heappush(heap, (heightMap[i][j], i, j))\n                    visited[i][j] = 1\n        \n        result = 0\n        while heap:\n            height, i, j = heapq.heappop(heap)    \n            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n                if 0 <= x < m and 0 <= y < n and not visited[x][y]:\n                    result += max(0, height-heightMap[x][y])\n                    heapq.heappush(heap, (max(heightMap[x][y], height), x, y))\n                    visited[x][y] = 1\n        return result\n```\n\nThe idea is that we maintain all the points of the current border in a min heap and always choose the point with the lowest length. This is actually an optimized searching strategy over the trivial brute force method: instead of dfs each point to find the lowest "border" of its connected component, we can always start a search from the lowest border and update the points adjacent to it.
[]