Very Straightforward C++ Solution
```\n/\nthe idea is to apply the bucket principal:\n1. a bucket is composed of bars to hold water\n2. the hight of the water the bucket can hold must equal to t
```\n/*\nthe idea is to apply the bucket principal:\n1. a bucket is composed of bars to hold water\n2. the hight of the water the bucket can hold must equal to the lowest bar of the bucket\nexample: for a matrix:\n[[12,13,1,12],\n [13,4,13,12],\n [13,8,10,12],\n [12,13,12,12],\n [13,13,13,13]]\n\nthe ans is 14\n\nthe trick is to find the smallest bar to hold water for any given square,\n\nnote in the above example, the square at position (1,1) can hold 8 water,\nthis is computed by the lowest height of the 4 bars surrounding it:\ntop bar of (1,1) is 13, left bar is 13, right bar is 13, bottom bar is 12 (not 13),\n\nthe bottom bar is 12 not 13 because the bottom bar of (1,1) is determined by the lowest bars\nof its surroundings. And the lowest right bar for position (2,1), the position\ndirectly below (1,1), is 12, which determined the bottom bar of (1,1) to be 12.\n\nalgorithm:\n1. the elements on the 4 sides of the matrix can be considered at tentative bars for the bucket\n2. maintain a priority queue (min heap) and extract the smallest value (bar) in a loop\n3. we also maintain the max value M extracted for the height of the lowest bar\n4. while extracting the smallest value, we also visit all the surrounding squares (left, right, up, down)\n5. if a visited square has height H smaller than M, then water can be trapped at this square at amount (M-H)\n5. this is bc M must be the lowest bar amoung other bars to trap water for this square, since we always visit the lowest element first with the min heap\n6. add the water up to get the total amount of water that could be trapped\n\n*/\n//T(n) = O(m*n), bc each node will be put in and extracted out from the heap only once\n//S(n) = O(m*n)\nclass Solution {\npublic:\n    int trapRainWater(vector<vector<int>>& heightMap) {\n        if(heightMap.empty()){return 0;}\n        //step 1:\n        priority_queue<pip, vector<pip>, comp> minHeap;\n\n        int m = heightMap.size();\n        int n = heightMap[0].size();\n        \n        vector<vector<bool>> visited(m, vector<bool>(n,false));//record the visited nodes\n        \n        for(int r = 0; r < m; r++){\n            minHeap.push({heightMap[r][0],{r,0}});\n            minHeap.push({heightMap[r][n-1],{r,n-1}});\n            visited[r][0] = true;\n            visited[r][n-1] = true;\n        }\n        for(int c = 1; c < n-1; c++){\n            minHeap.push({heightMap[0][c],{0,c}});\n            minHeap.push({heightMap[m-1][c],{m-1,c}});\n            visited[0][c] = true;\n            visited[m-1][c] = true;\n        }\n        //steps 2-6:\n        int Max = minHeap.top().first;//update when a larger bar is extracted\n        int res = 0;//add or update when a visited square has height lower than Max\n        \n        static vector<vector<int>> directions = {{0,1},{0,-1},{1,0},{-1,0}};\n        \n        while(!minHeap.empty()){\n            auto u = minHeap.top();\n            minHeap.pop();\n            int u_h = u.first;\n            int u_r = u.second.first;\n            int u_c = u.second.second;\n            Max = max(Max, u_h);\n            for(auto d : directions){\n                int x = u_r + d[0];\n                int y = u_c + d[1];\n                if(x>0 && x<m && y>0 && y<n && !visited[x][y]){\n                    visited[x][y] = true;\n                    if(heightMap[x][y] < Max){\n                        res += Max - heightMap[x][y];\n                    }\n                    minHeap.push({heightMap[x][y],{x,y}});\n                }\n            }\n        }\n        return res;\n    }\nprivate:\n    using pip = pair<int,pair<int,int>>;\n    struct comp{\n        bool operator()(const pip& a, const pip& b)const{\n            return a.first > b.first;\n        }\n    };\n};
[]