MinHeap+ BFS||Why 1D methods not working?||33ms Beats 97.42%
Intuition\n Describe your first thoughts on how to solve this problem. \nBFS+ minHeap(priority_queue) over int3=tuple<int, int, int>\n\nIn fact, this solution i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBFS+ minHeap(priority_queue) over `int3=tuple<int, int, int>`\n\nIn fact, this solution is made for 2D case & is applicable to 1D case. (cf. [Leetcode 42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/solutions/5010020/monotonic-stack-vs-priority-queueusing-pyplot-explain3ms-beats-9910/))\n\n# Why 1D methods not working?\n2-pointer & monotonic stack methods work well for 1D question, but hard to generalize to 2D case. ****Boundary in 1D space means 2 points, just left & right; Boundary in 2D space means a contour.****\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe tuple `(height, i, j)` will be pushed to the minHeap `pq`. Push the cell data on the boundary all to the `pq`.\nUse BFS to fill the water when current height `currH` is below `water_level`.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nm\\log(mn))$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$\n# Code\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    using int3=tuple<int, int, int>;\n    const int di[4]={1,-1,0, 0};\n    const int dj[4]={0, 0,1,-1};\n    int trapRainWater(vector<vector<int>>& height) {\n        int m=height.size(), n=height[0].size();\n        vector<int3> boundary;\n        boundary.reserve(2*(m+n));\n        for(int i=0; i<m; i++) {\n            boundary.emplace_back(height[i][0], i, 0); \n            boundary.emplace_back(height[i][n-1], i, n-1);\n            height[i][0]=height[i][n-1]=-1;//visited\n        }\n            \n        for(int j=0; j<n; j++){\n            boundary.emplace_back(height[0][j], 0, j); \n            boundary.emplace_back(height[m-1][j], m-1, j);\n            height[0][j]=height[m-1][j]=-1;//visited\n        }\n            \n        priority_queue<int3, vector<int3>, greater<int3>> pq(boundary.begin(), boundary.end());\n\n        int ans=0, water_level=0;\n        while (!pq.empty()){\n            auto [h, i, j]=pq.top();\n            pq.pop();\n            water_level=max(water_level, h);\n            for (int k=0; k<4; k++){\n                int i0=i+di[k], j0=j+dj[k];\n                if (i0<=0|| i0>=m-1||j0<=0||j0>=n-1||height[i0][j0]==-1) continue;\n                int currH=height[i0][j0];\n                pq.push({currH, i0, j0});\n                if (currH< water_level)\n                    ans+=water_level-currH;\n                height[i0][j0]=-1;\n            }\n        }\n        return ans; \n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n       \n```
['Breadth-First Search', 'Heap (Priority Queue)', 'C++']