[Python3][Visualization] BFS Solution With Explanation
Cells which can trap the rain water, must be surrounded by cells with higher heights. We can maintain a level and increases1 by 1 from 0. At the same time, use 
Cells which can trap the rain water, must be surrounded by cells with higher heights. We can maintain a `level` and increases1 by 1 from 0. At the same time, use BFS with a Min-Heap to iterate each cell. \n<br/>\n\n# Graph\n<ins>**Green**</ins>: The cell added in the heap\n<ins>**Yellow**</ins>: The current cell\n<ins>**Blue**</ins>: The cell is connecting to the current cell and is added to the heap\n<ins>**Red**</ins>: The cell popped out from the heap\n<ins>**White**</ins>: The cell has not been visited yet\n\n<br/>\n\n# Initial \n![image](https://assets.leetcode.com/users/images/6bb154bb-4ee6-46aa-a224-2830f4032065_1617311493.8818207.png)\n\nCells which can trap the rain water, must be surrounded by cells with higher heights, so board cells cannot trap the water. Let\'s add those cells to the heap first (Sorted by height).\n\n<br/>\n\n# Level 1\n![image](https://assets.leetcode.com/users/images/d09ed0b6-644d-44bf-bdca-df5d1ee93505_1617312579.7180874.png)\n\nCells with the lowest height will be popped out. In this case, there are 3 cells with height 1 will be popped out. The Order doesn\'t matter. \n\n## Graph 1.1\nCell[0,0] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 1.2\nCell[0,3] is popped out from the heap. Cell[1,3] height is larger than level(1). Added Cell[1,3] to the heap.\n\n## Graph 1.3\nCell[2,5] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n<br/>\n\n# Level 2\n![image](https://assets.leetcode.com/users/images/4ad207b8-0fa3-450a-8d41-dc67b46e4453_1617313986.078711.png)\n\nThere is no level 1 cell in the heap, so set level = 2. There are 3 cells with height 2 will be popped out. The Order doesn\'t matter. \n\n## Graph 2.1\nCell[2,0] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 2.2\nCell[0,5] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 2.3\nCell[2,3] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n<br/>\n\n# Level 3\n![image](https://assets.leetcode.com/users/images/58e12565-a4d7-4ce3-9181-be332d114ab0_1617316339.6603253.png)\n\nThere is no level 2 cell in the heap, so set level = 3. There are 7 cells with height 3 will be popped out. The Order doesn\'t matter. \n\n## Graph 3.1\nCell[0,4] is popped out from the heap. Cell[1,4] height is smaller than level(3). <ins>**Cell[1,4] can trap rain water: Level(3) - Cell[1,4] height(2) = 1**</ins>. Added Cell[1,4] to the heap.\n\n## Graph 3.2\nCell[1,4] is popped out from the heap, since it has the lowest height 2. There is no non-visited cells connecting to it.\n\n## Graph 3.3\nCell[0,2] is popped out from the heap. Cell[1,2] height is smaller than level(3). <ins>**Cell[1,2] can trap rain water: Level(3) - Cell[1,2] height(1) = 2**</ins>. Added Cell[1,2] to the heap.\n\n## Graph 3.4\nCell[1,2] is popped out from the heap, since it has the lowest height 1. Cell[1,1] height is smaller than level(3). <ins>**Cell[1,1] can trap rain water: Level(3) - Cell[1,1] height(2) = 1**</ins>. Added Cell[1,1] to the heap.\n\n## Graph 3.5\nCell[1,1] is popped out from the heap, since it has the lowest height 2. There is no non-visited cells connecting to it.\n\n## Graph 3.6\nCell[1,0] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 3.7\nCell[1,3] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 3.8\nCell[2,1] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 3.9\nCell[2,2] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 3.10\nCell[2,4] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n<br/>\n\n# Level 4\n![image](https://assets.leetcode.com/users/images/cdfcb385-c731-4127-a9c8-322d075243fc_1617316201.9357524.png)\n\nThere is no level 3 cell in the heap, so set level = 4. There are 2 cells with height 4 will be popped out. The Order doesn\'t matter. \n\n## Graph 4.1\nCell[0,1] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n## Graph 4.2\nCell[1,5] is popped out from the heap, and there is no non-visited cells connecting to it.\n\n<br/>\n\n# Summary\n<ins>**Volume of water**</ins>: 1 + 2 + 1 = 4\n\n<br/>\n\n# Code\n```\nclass Solution:\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        if not heightMap or not heightMap[0]:\n            return 0\n\t\t\t\n\t\t\t\n\t\t# Initial\n\t\t# Board cells cannot trap the water\n        m, n = len(heightMap), len(heightMap[0])\n        if m < 3 or n < 3:\n            return 0\n\t\t\t\n\t\t\t\n\t\t# Add Board cells first\n        heap = []\n        for i in range(m):\n            for j in range(n):\n                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n                    heapq.heappush(heap, (heightMap[i][j], i, j))\n                    heightMap[i][j] = -1\n\t\t\t\t\t\n\t\t\t\t\t\n\t\t# Start from level 0\n        level, res = 0, 0\n        \n\t\twhile heap:\n            height, x, y = heapq.heappop(heap)\n            level = max(height, level)\n\n            for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n                if 0 <= i < m and 0 <= j < n and heightMap[i][j] != -1:\n                    heapq.heappush(heap, (heightMap[i][j], i, j))\n\t\t\t\t\t\n\t\t\t\t\t# If cell\'s height smaller than the level, then it can trap the rain water\n                    if heightMap[i][j] < level:\n                        res += level - heightMap[i][j]\n\t\t\t\t\t\t\n\t\t\t\t\t# Set the height to -1 if the cell is visited\n                    heightMap[i][j] = -1\n\n        return res\n```\n\n\n\nAll good? ^v^ Now you can try a smiliar quesion: [778. Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/)
['Breadth-First Search', 'Heap (Priority Queue)', 'Python3']