python3 solution with detailed explanation
I mimick the way water flows. On every point, I assume there will be the maximum amount of water (which is the maximum in the heightMap) falls down. Then the wa
I mimick the way water flows. On every point, I assume there will be the maximum amount of water (which is the maximum in the heightMap) falls down. Then the water will look for the lowest point on edge to excape. \n\nFrom the current point, water will go to four directions untill it meets the edge. Once it meet the edge, the water that can be trapped will be the min(edge, trap). I record the path that the water goes. If the new point is lower than the current trappable water, then it will be added to the path. So that the water this path can trap is trap * len(pathVal) - sum(pathHeight)\n\nThere is a situation that the lowest edge may not appear so that we may add the higher points to the path. In this case, the trappable water will be less than some of the height in the path. If so, I use the highest height in the path as the trappable water amount and do the whole process all over again.\n\n```\nclass Solution:\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        \n        def flow(path,pathVal,edge,i,j,heightMap):\n            global trap\n            if (i,j) not in path:\n                if (i,j) in edge:\n\t\t\t\t#if the edge is lower than the trappable water, then update the trappable water\n                    trap = min(trap,heightMap[i][j])\n                else:\n                    if heightMap[i][j] < trap:\n                        path.add((i,j))\n                        pathVal.append(heightMap[i][j])\n                        flow(path,pathVal,edge,i-1,j,heightMap)\n                        flow(path,pathVal,edge,i+1,j,heightMap)\n                        flow(path,pathVal,edge,i,j+1,heightMap)\n                        flow(path,pathVal,edge,i,j-1,heightMap)\n\t\t\t\t\t\t\n        #get the most trappable water amount\n        maxTrap = 0\n        for i in range(len(heightMap)):\n            temp = max(heightMap[i])\n            maxTrap = max(temp,maxTrap)\n        edge = set()\n        for i in range(len(heightMap)):\n            edge.add((i,0))\n            edge.add((i,len(heightMap[0])-1))\n        for i in range(len(heightMap[0])):\n            edge.add((0,i))\n            edge.add((len(heightMap)-1,i))\n        \n        result = 0\n        for i in range(len(heightMap)):\n            for j in range(len(heightMap[0])):\n                if (i,j) not in edge:\n                    global trap \n                    trap = maxTrap\n                    pathVal = []\n                    path = set()\n                    flow(path,pathVal,edge,i,j,heightMap)\n\t\t\t\t\t#if the trappable water is lower than any of the height in the path, we need to reset the trappable water to the hightest height in the path and restart our process\n                    while pathVal and trap < max(pathVal):\n                        trap = max(pathVal)\n                        pathVal = []\n                        path = set()\n                        flow(path,pathVal,edge,i,j,heightMap)\n                    add = trap * len(pathVal) - sum(pathVal)\n\t\t\t\t\t#Once we done with the path, there is no need to check again, consider those points as the edge\n                    edge.update(path)\n                    result += add\n                    \n        return result\n```\n\n
[]