Trapping Rain Water II

Problem Statement

The task revolves around calculating the volume of water trapped on a 2D topographic map after rainfall. Specifically, we are given a matrix named heightMap where each element represents the elevation of a square unit cell of the terrain. The goal is to calculate the total volume of water that remains trapped between the elevated regions of the map post-rain. The matrix dimensions, m x n, depict the size of the elevation map. This computational challenge involves dealing with spatial structures on a grid and determining the interaction between them when subjected to water accumulation scenarios.

Examples

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.

Example 2

Input:

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]]

Output:

10

Constraints

• m == heightMap.length
• n == heightMap[i].length
• 1 <= m, n <= 200
• 0 <= heightMap[i][j] <= 2 * 104

Approach and Intuition

Understanding the water trapping on a 2D map can be visualized similar to a 3D landscape where rain falls uniformly over the area. Post-rain, some areas of the map, depending on their surrounding elevation, will collect and hold water. Here's how we can intuit the process:

1. Identify low points in the map where water is likely to collect. These points will typically be surrounded by higher points on all sides.
2. Expand outward from these initial low points, checking neighbors to determine if they can also hold water without spilling over to a lower height.
3. As we inspect each cell, calculate the water volume it can hold by comparing its height with its immediate surroundings. The difference in height, if surrounded by higher cells, determines the depth of the trapped water in that cell.
4. Accumulate the volume for all cells that trap water.

• Example Interpretations based on the examples provided:

  • For example 1 from the input [[1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1]], visualize a small basin where there are pockets (depicted by lower numbers surrounded by higher numbers). After simulating rain, these pockets trap water. The volume, in this case, was calculated as 4 units.
  • In a more substantial case like example 2 with a deeper center at level 1 and surrounded by walls of 3s, the water trapped is greater. The calculation provided the trapped volume as 10 units, showcasing a more extensive central pool.

• These examples adhere strictly to the constraints that the matrix is at least 1x1 and at most 200x200 with the heights of each cell ranging from 0 to 20000, ensuring that computations remain manageable yet potentially detailed and complex depending on the landscape given.

Solutions

class Solution {
public:
    int calculateWaterTrapping(vector<vector<int>>& elevationMap) {
        // Direction vectors
        int deltaRow[4] = {0, 0, -1, 1};
        int deltaCol[4] = {-1, 1, 0, 0};
    
        int rows = elevationMap.size();
        int cols = elevationMap[0].size();
    
        vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    
        // Min-heap to store the boundary cells
        priority_queue<WaterCell> edges;
    
        // Process the boundary by adding the first and last column of each row
        for (int r = 0; r < rows; r++) {
            edges.push(WaterCell(elevationMap[r][0], r, 0));
            edges.push(WaterCell(elevationMap[r][cols - 1], r, cols - 1));
            seen[r][0] = seen[r][cols - 1] = true;
        }
    
        // Process the boundary by adding the first and last row
        for (int c = 0; c < cols; c++) {
            edges.push(WaterCell(elevationMap[0][c], 0, c));
            edges.push(WaterCell(elevationMap[rows - 1][c], rows - 1, c));
            seen[0][c] = seen[rows - 1][c] = true;
        }
    
        int trappedWater = 0;
    
        while (!edges.empty()) {
            WaterCell cell = edges.top();
            edges.pop();
    
            int currentR = cell.row;
            int currentC = cell.col;
            int boundaryHeight = cell.height;
    
            for (int d = 0; d < 4; d++) {
                int nr = currentR + deltaRow[d];
                int nc = currentC + deltaCol[d];
    
                if (isWithinBounds(nr, nc, rows, cols) && !seen[nr][nc]) {
                    int neighborHeight = elevationMap[nr][nc];
    
                    if (neighborHeight < boundaryHeight) {
                        trappedWater += boundaryHeight - neighborHeight;
                    }
    
                    edges.push(WaterCell(max(neighborHeight, boundaryHeight), nr, nc));
                    seen[nr][nc] = true;
                }
            }
        }
    
        return trappedWater;
    }
    
private:
    class WaterCell {
    public:
        int height;
        int row;
        int col;
    
        WaterCell(int h, int r, int c) : height(h), row(r), col(c) {}
    
        bool operator<(const WaterCell& other) const {
            return height > other.height; // Min-heap by reversing comparison
        }
    };
    
    bool isWithinBounds(int row, int col, int maxRows, int maxCols) {
        return row >= 0 && col >= 0 && row < maxRows && col < maxCols;
    }
};