Priority_queue - Question 3

Leetcode 407. Trapping Rain Water II

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.

Constraints:

m == heightMap.length

n == heightMap[i].length

1 <= m, n <= 200

0 <= heightMap[i][j] <= 2 * 10^4

Analysis:

If you have a bucket built with pieces of woods, then the amount of water is determined by the wood with the lowest height.

So we view the two D matrix as a square bucket. 

The first step is to put all the elements in the peripheral into a reversed prority_queue (pq), which serves as the "wall" of the bucket.

Then start with the smallest elements, we can do a bfs search;

1. all the smaller elements should have contributions, the magnitude is the height diff;

2.  all the larger or equal elements become the "new walls", so keep them in the pq.

In step 1, we can do a second bfs, to make sure all the connected lower elements are counted. The higher ones becomes the "new walls" of the bucket, which are saved in the pq.

To avoid redundant visit, we can use a visit matrix to label the visit information.

See the code below:

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int res = 0, m = heightMap.size(), n = heightMap.front().size();
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        vector<vector<int>> vis(m, vector<int>(n, 0));
        for(int i=0; i<m; ++i) {
            pq.push({heightMap[i][0], i, 0});
            pq.push({heightMap[i][n-1], i, n-1});
            vis[i][0] = 1;
            vis[i][n-1] = 1;
        }
        for(int i=1; i<n-1; ++i) {
            pq.push({heightMap[0][i], 0, i});
            pq.push({heightMap[m-1][i], m-1, i});
            vis[0][i] = 1;
            vis[m-1][i] = 1;
        }
        vector<int> dirs = {-1, 0, 1, 0, -1};
        while(pq.size()) {
            auto t = pq.top();
            pq.pop();
            for(int i=0; i+1<dirs.size(); ++i) {
                int x = t[1] + dirs[i], y = t[2] + dirs[i+1];
                if(x<0 || x>=m || y<0 || y>=n || vis[x][y]) continue;
                int h = heightMap[x][y];
                if(h < t[0]) {
                    queue<vector<int>> pq2;
                    pq2.push({h, x, y});
                    res += t[0] - h;
                    vis[x][y] = 1;
                    while(pq2.size()) {
                        auto t2 = pq2.front();
                        pq2.pop();
                        for(int i2=0; i2+1<dirs.size(); ++i2) {
                            int x2 = t2[1] + dirs[i2], y2 = t2[2] + dirs[i2+1];
                            if(x2<0 || x2>=m || y2<0 || y2>=n || vis[x2][y2]) continue;
                            int h2 = heightMap[x2][y2];
                            if(h2 < t[0]) {
                                res += t[0] - h2;
                                pq2.push({h2, x2, y2});
                            }
                            else pq.push({h2, x2, y2});
                            vis[x2][y2] = 1;
                        }
                    }
                    continue;
                }
                pq.push({h, x, y});
                vis[x][y] = 1;
            }
        }
        return res;
    }
};

 

[code update, 2021-12-25]

The above code is not clean enough, see the updated one below:

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int res = 0, m = heightMap.size(), n = heightMap.front().size();
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        vector<vector<int>> vis(m, vector<int>(n, 0));
        for(int i=0; i<m; ++i) {
            pq.push({heightMap[i][0], i, 0});
            pq.push({heightMap[i][n-1], i, n-1});
            vis[i][0] = 1;
            vis[i][n-1] = 1;
        }
        for(int i=1; i<n-1; ++i) {
            pq.push({heightMap[0][i], 0, i});
            pq.push({heightMap[m-1][i], m-1, i});
            vis[0][i] = 1;
            vis[m-1][i] = 1;
        }
        vector<int> dirs = {-1, 0, 1, 0, -1};
        while(pq.size()) {
            auto t = pq.top();
            pq.pop();
            queue<vector<int>> q;
            q.push({t[1], t[2]});
            while(q.size()) {
                auto t2 = q.front();
                q.pop();
                for(int i=0; i+1<dirs.size(); ++i) {
                    int x = t2[0] + dirs[i], y = t2[1] + dirs[i+1];
                    if(x<0 || x>=m || y<0 || y>=n || vis[x][y]) continue;
                    int h = heightMap[x][y];
                    if(h < t[0]) {
                        res += t[0] - h;
                        q.push({x, y});
                    }
                    else pq.push({h, x, y});
                    vis[x][y] = 1;
                }
            }
        }
        return res;
    }
};

Upper Layer