Python C++BFS /heap解Leetcode難題407 Trapping Rain Water II

Py3 cpp BFS /heap解Leetcode難題407 Trapping Rain Water II

解題要訣:boundary由外而內，容器採min heap，BFS走訪

[Py3解請進]

-----

Tips for solving problems: boundary from outside toward inside, container using min heap, BFS transversal

[codes on Leetcode]https://leetcode.com/problems/trapping-rain-water-ii/solutions/6300513/bfs-over-min-heap11ms-beats-9890-by-anwe-qwz4/

[Tree/Graph Playlist]https://www.youtube.com/watch?v=bna7aw7dkPY&list=PLYRlUBnWnd5Kt0-3un43cwY6yT_il8NWe

class Solution:
    def trapRainWater(self, height: List[List[int]]) -> int:
        dir = (0, 1, 0, -1, 0)
        m, n = len(height), len(height[0])
        if m <= 2 or n <= 2:
            return 0

        boundary = []
        for i in range(m):
            boundary.append((height[i][0], i, 0))
            boundary.append((height[i][-1], i, n - 1))
            height[i][0] = height[i][-1] = -1

        for j in range(1, n - 1):
            boundary.append((height[0][j], 0, j))
            boundary.append((height[-1][j], m - 1, j))
            height[0][j] = height[-1][j] = -1

        heapify(boundary)
        ans, water_level = 0, 0

        while boundary:
            h, i, j = heappop(boundary)

            water_level = max(water_level, h)

            for a in range(4):
                i0, j0 = i + dir[a], j + dir[a + 1]
                if i0 < 0 or i0 >= m or j0 < 0 or j0 >= n or height[i0][j0] == -1:
                    continue
                currH = height[i0][j0]
                if currH < water_level:
                    ans += water_level - currH

                height[i0][j0] = -1
                heappush(boundary, (currH, i0, j0))
        return ans