<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:
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> border;

    // Keeping borders and bouring water on border with minimum height
    int trapRainWater(vector<vector<int>>& heightMap) {
        int rows = heightMap.size(), cols = heightMap[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0 || j == 0 || i == rows - 1 || j == cols - 1)
                border.push({heightMap[i][j], {i, j}});
            }
        }

        vector<vector<int>> visited(rows, vector<int>(cols, -1));
        while (!border.empty()) {
            int height = border.top().first;
            int row = border.top().second.first;
            int col = border.top().second.second;
            border.pop();
            if (visited[row][col] == -1) {
                dfs(heightMap, visited, row, col, height);
            }
        }

        int answer = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                answer += (visited[i][j] - heightMap[i][j]);
            }
        } 
        return answer;
    }

    void dfs(vector<vector<int>>& heightMap, vector<vector<int>>& visited, int row, int col, int height) {
        visited[row][col] = height;
        int rowMoves[] = {-1, 0, 0, 1};
        int colMoves[] = {0, -1, 1, 0};
        int rows = visited.size();
        int cols = visited[0].size();
        for (int i = 0; i < 4; i++) {
            int nextRow = row + rowMoves[i];
            int nextCol = col + colMoves[i];
            bool underBorder = cordinateUnderBorder(heightMap.size(), heightMap[0].size(), nextRow, nextCol);
            if (underBorder && visited[nextRow][nextCol] == -1 && heightMap[nextRow][nextCol] <= height) {
                dfs(heightMap, visited, nextRow, nextCol, height);
            } else if (underBorder && visited[nextRow][nextCol] == -1) {
                border.push({heightMap[nextRow][nextCol], {nextRow, nextCol}});
            }
        }

    }

    bool cordinateUnderBorder(int rows, int cols, int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
        return true;
    }

    // Per layer water trapped approach 
    // int trapRainWaterPerLayerApproach(vector<vector<int>>& heightMap) {
    //     int rows = heightMap.size(), cols = heightMap[0].size(), layers = INT_MIN;
    //     for (int i = 0; i < rows; i++) {
    //         for (int j = 0; j < cols; j++) {
    //             if (heightMap[i][j] > layers) layers = heightMap[i][j];
    //         }
    //     }

    //     int answer = 0;
    //     for (int layer = 0; layer < layers; layer++) {
    //         answer += countTrappedCellsInLayer(heightMap, layer);
    //     }
    //     return answer;
    // }

    // int countTrappedCellsInLayer(vector<vector<int>>& heightMap, int layer) {
    //     int answer = 0, rows = heightMap.size(), cols = heightMap[0].size();
    //     vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    //     for (int row = 1; row < rows - 1; row++) {
    //         for (int col = 1; col < cols - 1; col++) {
    //             if (!visited[row][col] && heightMap[row][col] <= layer) {
    //                 answer += countTrappedCells(heightMap, visited, row, col, layer);
    //             }
    //         }
    //     }
    //     return answer;
    // }

    // int countTrappedCells(vector<vector<int>>& heightMap, vector<vector<bool>>& visited, int row, int col, int layer) {
    //     visited[row][col] = true;
    //     int rows = heightMap.size(), cols = heightMap[0].size();
    //     if (row == rows - 1 || col == cols - 1 || row == 0 || col == 0) return 0;

    //     int rowMoves[] = {-1, 0, 0, 1};
    //     int colMoves[] = {0, -1, 1, 0};
    //     int answer = 0, overflow = 0;
    //     for (int i = 0; i < 4; i++) {
    //         int nextRow = row + rowMoves[i];
    //         int nextCol = col + colMoves[i];
    //         if (!visited[nextRow][nextCol] && heightMap[nextRow][nextCol] <= layer) {
    //             int trappedCells = countTrappedCells(heightMap, visited, nextRow, nextCol, layer);
    //             if (trappedCells == 0) {
    //                 overflow = 1;
    //             }
    //             answer += trappedCells;
    //         }
    //     }

    //     return overflow ? 0 : answer + 1;
    // }
};
30443