BFS over min heap using make_heap+pack||C++11ms beats 98.90%
IntuitionThis question is solved long ago by using priority_queue.C++ Python are made.For revisiting, it is changed into make_heap + pack info into an uint
it's
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
This question is solved long ago by using priority_queue.

C++ Python are made.

For revisiting, it is changed into make_heap + pack info into an uint
it's to mention, the method such as monotonic stack solving [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/solutions/5010020/monotonic-stack-vs-priority-queue-using-pyplot-explain-3ms-beats-99-10/) cannot  work for this question.
# Approach
<!-- Describe your approach to solving the problem. -->
[Please turn on English subtitles if necessary]
[https://youtu.be/n4Gq0DnT9Oc?si=VQcnCsGTa_-ixs_z](https://youtu.be/n4Gq0DnT9Oc?si=VQcnCsGTa_-ixs_z)
1. Declare 4-elemented arrays `di, dj` as global variables
2. Define `unsigned pack(unsigned h, unsigned i, unsigned j)` to pack the info data `(h, i, j)` to an uint
3. Define `array<int, 3> unpack(unsigned info)` to recover the data from the packed info
4. In `int trapRainWater(vector<vector<int>>& height)`, let `m=|height|, n=|height[0]|`
5. return 0 for the special case `m<=2 or n<=2`
6. Construct the 1D dynamic array `boundary`& reserve the space for it
7. Add boundary cells  and mark them as visited by using loops
8. Apply `make_heap` to `boundary` wrt ordering greater() to make it a min heap
9. Use BFS to fill the water when current height `currH` is below `water_level`. Use the conditional while  loop to proceed as follows
```
while (!boundary.empty()) {
    // Extract the smallest element from the heap
    pop_heap(boundary.begin(), boundary.end(), greater<>());
    unsigned info = boundary.back();
    boundary.pop_back(); // pop

    auto [h, i, j] = unpack(info);// extract data
    water_level = max(water_level, h);

    // Process adjacent cell
    for (int k = 0; k < 4; k++) {
        int i0 = i + di[k], j0 = j + dj[k];
        if (i0 < 0 || i0 >= m || j0 < 0 || j0 >= n ||
            height[i0][j0] == -1)// outside or visited
            continue;

        int currH = height[i0][j0];
        if (currH < water_level)// fill with water
            ans += water_level - currH;

        // Mark the cell as visited and push it to the heap
        height[i0][j0] = -1;
        boundary.push_back(pack(currH, i0, j0));
        push_heap(boundary.begin(), boundary.end(), greater<>());
    }
}

```
10. return `ans`
11. Python is made which is much shorter

# Why 1D methods not working?
2-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.****
# Real RUN for testcases
Consider the testcase `[[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]]` add some ouput below the line updating ans, one obtain 
```
water_level=1 currH=13 i0=1 j0=2 ans=0
water_level=12 currH=10 i0=2 j0=2 ans=2
water_level=12 currH=12 i0=3 j0=2 ans=2
water_level=12 currH=8 i0=2 j0=1 ans=6
water_level=12 currH=13 i0=3 j0=1 ans=6
water_level=12 currH=4 i0=1 j0=1 ans=14
```
The other testcase is `[[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]]` its process is as follows
```
water_level=8 currH=1 i0=1 j0=6 ans=7
water_level=8 currH=0 i0=2 j0=6 ans=15
water_level=8 currH=0 i0=1 j0=7 ans=23
water_level=8 currH=0 i0=1 j0=5 ans=31
water_level=8 currH=0 i0=2 j0=5 ans=39
water_level=8 currH=0 i0=1 j0=4 ans=47
water_level=8 currH=0 i0=2 j0=4 ans=55
water_level=8 currH=0 i0=1 j0=3 ans=63
water_level=8 currH=0 i0=2 j0=3 ans=71
water_level=8 currH=0 i0=1 j0=2 ans=79
water_level=8 currH=0 i0=2 j0=2 ans=87
water_level=8 currH=0 i0=1 j0=1 ans=95
water_level=8 currH=0 i0=2 j0=1 ans=103
water_level=8 currH=0 i0=2 j0=7 ans=111
water_level=8 currH=0 i0=1 j0=8 ans=119
water_level=8 currH=0 i0=2 j0=8 ans=127
water_level=8 currH=0 i0=1 j0=9 ans=135
water_level=8 currH=0 i0=2 j0=9 ans=143
water_level=8 currH=0 i0=3 j0=1 ans=151
water_level=8 currH=0 i0=3 j0=2 ans=159
water_level=8 currH=0 i0=3 j0=3 ans=167
water_level=8 currH=0 i0=3 j0=4 ans=175
water_level=8 currH=0 i0=3 j0=5 ans=183
water_level=8 currH=0 i0=3 j0=6 ans=191
water_level=8 currH=0 i0=3 j0=7 ans=199
water_level=8 currH=0 i0=3 j0=8 ans=207
water_level=8 currH=0 i0=3 j0=9 ans=215
```
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(mn\log(mn))$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(mn)$
# Code ||C++ using make_heap+ pack 11ms beats 98.90%
```cpp []
const int di[4] = {1, -1, 0, 0};
const int dj[4] = {0, 0, 1, -1};
class Solution {
public:
    static unsigned pack(unsigned h, unsigned i, unsigned j) {
        return (h << 16) | (i << 8) | j;
    }

    static array<int, 3> unpack(unsigned info) {
        array<int, 3> ans;
        ans[0] = info >> 16, ans[1] = (info >> 8) & 255, ans[2] = info & 255;
        return ans;
    }

    static int trapRainWater(vector<vector<int>>& height) {
        const int m = height.size(), n = height[0].size();
        if (m <= 2 || n <= 2)
            return 0; // No trapped water possible

        vector<unsigned> boundary(2 * (m + n - 1));

        // Add boundary cells  mark  visited
        int idx = 0;
        for (int i = 0; i < m; i++) {
            boundary[idx++] = pack(height[i][0], i, 0);
            boundary[idx++] = pack(height[i][n - 1], i, n - 1);
            height[i][0] = height[i][n - 1] = -1; // visited
        }

        for (int j = 1; j < n - 1; j++) {
            boundary[idx++] = pack(height[0][j], 0, j);
            boundary[idx++]=pack(height[m - 1][j], m - 1, j);
            height[0][j] = height[m - 1][j] = -1; // visited
        }

        // Build a min-heap
        make_heap(boundary.begin(), boundary.end(), greater<>());

        int ans = 0, water_level = 0;

        while (!boundary.empty()) {
            // Extract the smallest element from the heap
            pop_heap(boundary.begin(), boundary.end(), greater<>());
            unsigned info = boundary.back();
            boundary.pop_back();

            auto [h, i, j] = unpack(info);
            water_level = max(water_level, h);

            // Process adjacent cell
            for (int k = 0; k < 4; k++) {
                int i0 = i + di[k], j0 = j + dj[k];
                if (i0 < 0 || i0 >= m || j0 < 0 || j0 >= n ||
                    height[i0][j0] == -1)
                    continue;

                int currH = height[i0][j0];
                if (currH < water_level)
                    ans += water_level - currH;

                // Mark the cell as visited and push it to the heap
                height[i0][j0] = -1;
                boundary.push_back(pack(currH, i0, j0));
                push_heap(boundary.begin(), boundary.end(), greater<>());
            }
        }

        return ans;
    }
};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();

```
# Python code
```
class Solution:
    def trapRainWater(self, height: List[List[int]]) -> int:
        dir = (0, 1, 0, -1, 0)
        m, n = len(height), len(height[0])
        if m <= 2 or n <= 2:
            return 0

        boundary = []
        for i in range(m):
            boundary.append((height[i][0], i, 0))
            boundary.append((height[i][-1], i, n - 1))
            height[i][0] = height[i][-1] = -1

        for j in range(1, n - 1):
            boundary.append((height[0][j], 0, j))
            boundary.append((height[-1][j], m - 1, j))
            height[0][j] = height[-1][j] = -1

        heapify(boundary)
        ans, water_level = 0, 0

        while boundary:
            h, i, j = heappop(boundary)

            water_level = max(water_level, h)

            for a in range(4):
                i0, j0 = i + dir[a], j + dir[a + 1]
                if i0 < 0 or i0 >= m or j0 < 0 or j0 >= n or height[i0][j0] == -1:
                    continue
                currH = height[i0][j0]
                if currH < water_level:
                    ans += water_level - currH

                height[i0][j0] = -1
                heappush(boundary, (currH, i0, j0))
        return ans
 

        
```
['Breadth-First Search', 'Heap (Priority Queue)', 'C++', 'Python3']