【LeetCode】接雨水

两道做过的有意思的题目。因为都是第一次做的时候没做出来。而且是挺有意思的题目。因此放到这里做个笔记。

https://leetcode.cn/problems/container-with-most-water/

https://leetcode.cn/problems/trapping-rain-water-ii/

inline int enc(int x, int y, int h){
    return ((h<<16)+((x+1)<<8)+y+1);
}
inline int decx(int n){
    return ((n >> 8) & 0xff) - 1;
}
inline int decy(int n){
    return (n & 0xff) - 1;
}
inline int dech(int n){
    return n >> 16;
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size();
        int n = heightMap[0].size();
        priority_queue<int, vector<int>, greater<int>> q;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            q.push(enc(0, i, heightMap[0][i]));
            q.push(enc(m - 1, i, heightMap[m - 1][i]));
            vis[0][i] = true;
            vis[m - 1][i] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            q.push(enc(i, 0, heightMap[i][0]));
            q.push(enc(i, n-1, heightMap[i][n-1]));
            vis[i][0] = true;
            vis[i][n - 1] = true;
        }
        vector<vector<int>>dirs(4);
        dirs[0] = {1, 0};
        dirs[1] = {-1, 0};
        dirs[2] = {0, 1};
        dirs[3] = {0, -1};
        int ans = 0;
        while (!q.empty()) {
            int poll = q.top();
            q.pop();
            int x = decx(poll);
            int y = decy(poll);
            int h = dech(poll);
            for (auto& d : dirs) {
                int nx = x + d[0];
                int ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (vis[nx][ny]) continue;
                if (h > heightMap[nx][ny]) ans += h - heightMap[nx][ny];
                q.push(enc(nx, ny, max(h, heightMap[nx][ny])));
                vis[nx][ny] = true;
            }
        }
        return ans;
    }
};