python3, BFS + Heap, 1D case & 2D case
see visualization of 2D case here: https://www.youtube.com/watch?v=cJayBq38VYw\n\npython\n"""1D case"""\nfrom heapq import *\n\nclass element(object):\n    def 
see visualization of 2D case here: https://www.youtube.com/watch?v=cJayBq38VYw\n\n``` python\n"""1D case"""\nfrom heapq import *\n\nclass element(object):\n    def __init__(self, index, height):\n        self.index = index\n        self.height = height\n    \n    def __lt__(self, other):\n        return self.height < other.height\n\nclass Solution:\n    def trap(self, height):\n        L = len(height)\n        if L <= 2: return 0\n        \n        heap, visited = [], set()\n        for i in 0, L-1:\n            heap.append(element(i, height[i]))\n            visited.add(i)\n        heapify(heap)\n        max_visited, water = 0, 0\n\n        while heap:\n            node = heappop(heap)\n            i, h = node.index, node.height\n            if h > max_visited:\n                max_visited = h\n            else:\n                water += max_visited - h\n            for ni in i-1, i+1:\n                if 0<=ni<L and ni not in visited:\n                    heappush(heap, element(ni, height[ni]))\n                    visited.add(ni)\n\n        return water\n```\n\n\n``` python\n"""2D case"""\nfrom heapq import *\n\nclass element(object):\n    def __init__(self, row, col, height):\n        self.row = row\n        self.col = col\n        self.height = height\n    \n    def __lt__(self, other):\n        return self.height < other.height\n\nclass Solution:\n    def trapRainWater(self, heightMap):\n        H = len(heightMap)\n        if H <= 2: return 0\n        W = len(heightMap[0])\n        if W <= 2: return 0\n        \n        heap, visited = [], set()\n        for r in 0, H-1:\n            for c in range(W):\n                heap.append(element(r, c, heightMap[r][c]))\n                visited.add((r, c))\n        for c in 0, W-1:\n            for r in range(1, H-1):\n                heap.append(element(r, c, heightMap[r][c]))\n                visited.add((r, c))\n        heapify(heap)\n        max_visited, water = 0, 0\n\n        while heap:\n            node = heappop(heap)\n            r, c, h = node.row, node.col, node.height\n            if h > max_visited:\n                max_visited = h\n            else:\n                water += max_visited - h\n            for nr, nc in (r-1, c), (r+1, c), (r, c-1), (r, c+1):\n                if 0<=nr<H and 0<=nc<W and (nr, nc) not in visited:\n                    heappush(heap, element(nr, nc, heightMap[nr][nc]))\n                    visited.add((nr, nc))\n\n        return water\n```
[]