407. Trapping Rain Water II

407. Trapping Rain Water II (Hard)

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

 

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

 

Constraints:

• 1 <= m, n <= 110
• 0 <= heightMap[i][j] <= 20000

Related Topics:
Heap, Breadth-first Search

Similar Questions:

• Trapping Rain Water (Hard)

Solution 1. Heap

// OJ: https://leetcode.com/problems/trapping-rain-water-ii/
// Author: github.com/lzl124631x
// Time: O(MNlog(MN))
// Space: O(MN)
// Ref: https://discuss.leetcode.com/topic/60914/concise-c-priority_queue-solution
class Solution {
    typedef array<int, 3> Point;
public:
    int trapRainWater(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, ans = 0, maxH = INT_MIN;
        priority_queue<Point, vector<Point>, greater<>> pq;
        vector<vector<bool>> seen(M, vector<bool>(N));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == 0 || i == M - 1 || j == 0 || j == N - 1) {
                    pq.push({ A[i][j], i, j });
                    seen[i][j] = true;
                }
            }
        }
        while (pq.size()) {
            auto [h, x, y] = pq.top();
            pq.pop();
            maxH = max(maxH, h);
            for (auto &[dx, dy] : dirs) {
                int a = x + dx, b = y + dy;
                if (a < 0 || a >= M || b < 0 || b >= N || seen[a][b]) continue;
                seen[a][b] = true;
                if (A[a][b] < maxH) ans += maxH - A[a][b];
                pq.push({ A[a][b], a, b });
            }
        }
        return ans;
    }
};