python with Queue.PriorityQueue

  • 0

    The key idea is to use a priority queue, which always returns the cell with lowest water level among along the border.
    Our border starts from the boundary of the whole rectangular, assuming there is no water along the boundary, and then narrows down the border little by little.

    class Solution(object):
        def trapRainWater(self, heightMap):
            :type heightMap: List[List[int]]
            :rtype: int
            m = len(heightMap)
            if m == 0:
                return 0
            n = len(heightMap[0])
            if n == 0:
                return 0
            visited = [[False for i in range(n)] for j in range(m)]
            from Queue import PriorityQueue
            q = PriorityQueue()
            for i in range(m):
                visited[i][0] = True
                visited[i][n-1] = True
            for j in range(1, n-1):
                visited[0][j] = True
                visited[m-1][j] = True
            S = 0
            while not q.empty():
                cell = q.get()
                for (i, j) in [(1,0), (-1,0), (0,1), (0,-1)]:
                    x = cell[1] + i
                    y = cell[2] + j
                    if x in range(m) and y in range(n) and not visited[x][y]:
                        S += max(0, cell[0] - heightMap[x][y])   # how much water at the cell
                        visited[x][y] = True
            return S

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.