<p>Given an <code>m x n</code> integer matrix <code>heightMap</code> representing the height of each unit cell in a 2D elevation map, return <em>the volume of water it can trap after raining</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/trap1-3d.jpg" style="width: 361px; height: 321px;" />
<pre>
<strong>Input:</strong> heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/trap2-3d.jpg" style="width: 401px; height: 321px;" />
<pre>
<strong>Input:</strong> heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
<strong>Output:</strong> 10
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == heightMap.length</code></li>
	<li><code>n == heightMap[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= heightMap[i][j] &lt;= 2 * 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    // Analysis 
    // Method1: naive method, 就是两维方法，往四个方向找最小值
    // 是错误的，因为有多条路可以通路

    // Method2: 从左上角往下推 (left+up->), 然后是有下角往上推。 或者四个方向推，也是错误的。。

    // method3: 从四周开始推，但是取最小的点。。然后推进。。

    int trapRainWater(vector<vector<int>>& heightMap) {
        int nRows = heightMap.size();
        int nCols = heightMap[0].size();

        vector<vector<int>> trappedWater;
        for (int i = 0; i < nRows; i++) {
            vector<int> v(nCols, -1);
            trappedWater.push_back(v);
        }

        priority_queue<pair<int, pair<int, int>>,
                     vector<pair<int, pair<int, int>>>, 
                     greater<pair<int, pair<int, int>>>> pq;

        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (i == 0 || i == (nRows-1) || j == 0 || j == (nCols-1)) {
                    pq.push({heightMap[i][j], {i, j}});
                    trappedWater[i][j] = 0;
                }
            }
        }

        int sum = 0;
        while (!pq.empty()) {
            vector<pair<int,int>> directions;
            directions.push_back({0, 1});
            directions.push_back({0,-1});
            directions.push_back({1,0});
            directions.push_back({-1,0});

            pair<int, pair<int, int>> cell = pq.top();
            int pathHeight = cell.first;
            int r = cell.second.first;
            int c = cell.second.second;
            pq.pop();

            for (auto dir : directions) {
                int r1 = r + dir.first;
                int c1 = c + dir.second;
                if (r1 >= 0 && r1 < nRows && c1 >= 0 && c1 < nCols) {
                    if (trappedWater[r1][c1] != -1) continue;

                    if (heightMap[r1][c1] < pathHeight) {
                        sum += pathHeight - heightMap[r1][c1];
                        trappedWater[r1][c1] = pathHeight - heightMap[r1][c1];

                        // acutal height to path
                         pq.push({pathHeight, {r1, c1}});

                    } else {
                        trappedWater[r1][c1] = 0;
                        // actual hieght:
                        pq.push({heightMap[r1][c1], {r1, c1}});
                    }
                }
            }
        }

           for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (trappedWater[i][j] > 0) {
                    cout << trappedWater[i][j] << " i = " << i << " j =" << j << endl;
                }
            }
            }


        return sum;

    }

    // int trapRainWater(vector<vector<int>>& heightMap) {
    //     int nRows = heightMap.size();
    //     int nCols = heightMap[0].size();
    //     int sum = 0;
        
    //     vector<vector<int>> leftUp, leftDown, rightUp, rightDown;
    //     for (int i = 0; i < nRows; i++) {
    //         vector<int> v(nCols, 0);
    //         leftUp.push_back(v);
    //         leftDown.push_back(v);
    //         rightDown.push_back(v);
    //         rightUp.push_back(v);
    //     }

    //     // leftUP -> rightDown
    //     for (int i = 1; i < nRows; i++) {
    //         for (int j = 1; j < nCols; j++) {
    //             leftUp[i][j] = min(max(leftUp[i-1][j],heightMap[i-1][j]),
    //                                max(leftUp[i][j-1], heightMap[i][j-1]));
    //         }
    //     }

    //     // leftDown -> rightUp
    //     for (int i = nRows-2; i >= 0; i--) {
    //         for (int j = 1; j < nCols; j++) {
    //             leftDown[i][j] = min(max(leftDown[i+1][j],heightMap[i+1][j]),
    //                                max(leftDown[i][j-1], heightMap[i][j-1]));
    //         }
    //     }

    //     // rightDown -> leftUP
    //     for (int i = nRows-2; i >= 0; i--) {
    //         for (int j = nCols-2; j>=0; j--) {
    //             rightDown[i][j] = min(max(rightDown[i+1][j],heightMap[i+1][j]),
    //                                max(rightDown[i][j+1], heightMap[i][j+1]));
    //         }
    //     }

    //      // rightUp -> leftDown
    //     for (int i = 1; i < nRows; i++) {
    //         for (int j = nCols-2; j>=0; j--) {
    //             rightUp[i][j] = min(max(rightUp[i-1][j],heightMap[i-1][j]),
    //                                max(rightUp[i][j+1], heightMap[i][j+1]));
    //         }
    //     }

    //     for (int i = 1; i < nRows-1; i++) {
    //         for (int j = 1; j < nCols-1; j++) {
    //             int delta = min(min(leftUp[i][j], rightDown[i][j]),
    //                             min(leftDown[i][j], rightUp[i][j])) - heightMap[i][j];
    //             if (delta > 0) {
    //                 cout << "delta: " << delta << " i= " << i << " j= " << j << endl; 
    //                 sum += delta;
    //             }
    //             cout << endl;
    //         }
    //     }
    //     return sum;
    // }


    // int trapRainWater(vector<vector<int>>& heightMap) {
    //     int nRows = heightMap.size();
    //     int nCols = heightMap[0].size();

    //     int sum = 0;
    //     for (int i = 1; i < nRows-1; i++) {
    //         for (int j = 1; j < nCols-1; j++) {
    //             // up
    //             int maxUp = heightMap[i][j];
    //             int k = i-1;
    //             while (k >= 0) {
    //                 if (heightMap[k][j] >= maxUp) {
    //                     maxUp = heightMap[k][j];
    //                 }
    //                 k--;
    //             }
    //             // down
    //             int maxDown = heightMap[i][j];
    //             k = i+1;
    //             while (k < nRows) {
    //                 if (heightMap[k][j] >= maxDown) {
    //                     maxDown = heightMap[k][j];
    //                 }
    //                 k++;
    //             }

    //             // left
    //             int maxLeft = heightMap[i][j];
    //             k = j-1;
    //             while (k >= 0) {
    //                 if (heightMap[i][k] >= maxLeft) {
    //                     maxLeft = heightMap[i][k];
    //                 }
    //                 k--;
    //             }

    //             // right;
    //             int maxRight = heightMap[i][j];
    //             k = j+1;
    //             while (k < nCols) {
    //                 if (heightMap[i][k] >= maxRight) {
    //                     maxRight = heightMap[i][k];
    //                 }
    //                 k++;
    //             }

    //             int minHeight = min(
    //                              min(maxLeft, maxRight),
    //                              min(maxUp, maxDown));

    //             int delta = (minHeight - heightMap[i][j]);
    //             if (delta > 0) {
    //                  cout << "delta: " << delta  << " " << i << " " << j << endl;
    //                  sum += delta;
    //             }
               
    //         }
    //     }

    //     return sum;
    // }
};
32943