19_jan

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

 

Example 1:


Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: 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.
*/

//approch
class Solution {
public:
    typedef pair<int, pair<int, int>> PP; // {height, {row, col}}
    vector<vector<int>> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size();
        if (m == 0) return 0;
        int n = heightMap[0].size();
        if (n == 0) return 0;

        priority_queue<PP, vector<PP>, greater<PP>> boundaryCells; // Min-heap
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        // Add boundary cells to the heap and mark them as visited
        for (int i = 0; i < m; i++) {
            for (int j : {0, n - 1}) {
                boundaryCells.push({heightMap[i][j], {i, j}});
                visited[i][j] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i : {0, m - 1}) {
                if (!visited[i][j]) { // Avoid adding corner cells twice
                    boundaryCells.push({heightMap[i][j], {i, j}});
                    visited[i][j] = true;
                }
            }
        }

        int water = 0;

        while (!boundaryCells.empty()) {
            auto [height, cell] = boundaryCells.top();
            boundaryCells.pop();

            int i = cell.first, j = cell.second;

            for (auto& dir : directions) {
                int ni = i + dir[0], nj = j + dir[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    water += max(0, height - heightMap[ni][nj]);
                    boundaryCells.push({max(height, heightMap[ni][nj]), {ni, nj}});
                    visited[ni][nj] = true;
                }
            }
        }

        return water;
    }
};