[C++] Explained why Trapping water solution doesn't work
\n/*\n    https://leetcode.com/problems/trapping-rain-water-ii/\n    \n    If you are thinking of converting the classic trapping rain water to this,\n    then 
```\n/*\n    https://leetcode.com/problems/trapping-rain-water-ii/\n    \n    If you are thinking of converting the classic trapping rain water to this,\n    then it might not work as expected. Lets say, for each position, you compute the\n    horizontal blocking height and the vertical blocking height. Now that you know the\n    blocking heights for all 4 dirs, you might think the volume computation from min of these\n    blocking heights will give the answer, but it won\'t give optimal answer.\n    \n    Reason being, that we are not considering the case when any of the connecting horizontal or\n    vertical blocks might have a way to drain the water.\n    \n    4 4 4 4\n    4 3 3 4\n    4 4 3 4,\n    Here as we can see even though horizontal and vertical blocking height logic seems to give ans = 1 (at (1, 1) block), in reality\n    it is 0. The block at (1, 2) will spill the water via (2, 2) and won\'t be able to hold any water, so the block at\n    (1, 1) won\'t be able to hold any water as well no matter what.\n    \n    Now how do we find the solution ?\n    What if we are able to find a way to approach a block via its min height blocking cell and then just check if the height of min block\n    cell is greater than curr. If it is greater, then curr cell can hold water, this is because we were able to reach the current cell via\n    the min height blocking cell and that means remaining blocking cells are all greater in height than this path cell. So if this path cell\n    is greater than current, then all other blocking cells are greater as well.\n    \n    Now to actually do this in practice, we make use of min heap. We add the initial border cells to heap. Then slowly start reaching the inner\n    cells via the shortest height boundary cells, while keeping track of tallest cell boundary in the path.\n    Each time we reach an inner cell, there are 2 possibilities:\n    1. Inner cell is greater, then we add this to heap as well. This can act as a blocking height for more inner cells.\n    2. Inner cell is smaller, then we know that this inner call can hold water = path_cell - inner_cell. Add this to heap as well\n    \n    While adding new elements to heap, make sure to add the max height of that path, since that is the actual boundary in that path.\n    \n    TC: O(MNlog(MN))\n    SC: O(MN)\n*/\nclass Solution {\npublic:\n\n    int trapRainWater(vector<vector<int>>& heights) {\n        int vol = 0;\n        const int M = heights.size(), N = heights[0].size();\n        vector<vector<bool>> visited(M, vector<bool>(N, false));\n        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n        \n        auto comp = [&](const array<int, 3>& a, const array<int, 3>& b) { return a[0] >= b[0]; };\n        \n        // <height, row, col>\n        priority_queue<array<int, 3>, vector<array<int, 3>>, decltype(comp)> min_heap(comp);\n        \n        // add all boundary cells\n        // top and bottom cells\n        for(int i = 0; i < N; i++) {\n            min_heap.push({heights[0][i], 0, i}),\n            min_heap.push({heights[M-1][i], M-1, i});\n            visited[0][i] = true, visited[M-1][i] = true;\n        }\n        \n        // right and left cells\n        for(int i = 0; i < M; i++) {\n            min_heap.push({heights[i][0], i, 0}),\n            min_heap.push({heights[i][N-1], i, N-1});\n            visited[i][0] = true, visited[i][N-1] = true;\n        }\n            \n        while(!min_heap.empty()) {\n            auto [height, row, col] = min_heap.top();\n            min_heap.pop();\n            \n            // explore the neighbouring cells\n            for(auto dir: directions) {\n                int r = row + dir[0], c = col + dir[1];\n                // process the inner cell\n                if(r >= 0 && r < M && c >= 0 && c < N && !visited[r][c]) {\n                    // mark current cell as visited\n                    visited[r][c] = true;\n                    // if current is smaller, it can store water\n                    if(heights[r][c] < height)\n                        vol += height - heights[r][c];\n                    \n                    min_heap.push({max(height, heights[r][c]), r, c});\n                }\n            }\n        }\n        return vol;\n    }\n};\n```
['C', 'C++']