407. Trapping Rain Water II

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

往高低不平的一堆相连的方柱注水，问最多能保持住多少水。是之前Trapping Rain Water I拓展到二维的情况，但解法并不只是对每个格子横竖都检查一遍就可以了，因为(i, j)能蓄多少水取决于j列能蓄多少水，而j列能蓄多少又取决于([0, i -1], j)，相互之间形成了dependency。虽然不能直接套用一维的解法，但基本原则是一样的：1. 每块能蓄多少水是由它（即使隔的很远）最高的一圈外围决定的；2. 又取决于那圈外围中最矮的高度。因此模拟不断增加高度从外往内漫水的过程，从最外层开始做BFS，维持一个global变量记录当前遍历过的最高高度mx。每次找Q中高度最小的块抛出并更新最高高度mx，模拟水位到了mx的情况，mx也就是外围中最矮高度。遍历它前后左右并压入Q做候选，如果邻居中找到了比当前块还低的块，意味着水位mx - height(neighbor)就是neighbor能蓄的水量。

/*
 * @lc app=leetcode id=407 lang=cpp
 *
 * [407] Trapping Rain Water II
 */

// @lc code=start
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty()) return 0;
        const int M = heightMap.size(), N = heightMap[0].size();
        // min heap
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        vector<vector<bool>> visited(M, vector<bool>(N, false));
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        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) {
                    q.push({heightMap[i][j], i * N + j});
                    visited[i][j] = true;
                }
            }
        }
        int mx = 0, res = 0;
        while (!q.empty()) {
            const auto t = q.top(); q.pop();
            const auto h = t.first, i = t.second / N, j = t.second % N;
            mx = max(mx, h);
            for (const auto &d : dirs) {
                const int x = i + d[0], y = j + d[1];
                if (x >= 0 && x < M && y >= 0 && y < N && !visited[x][y]) {
                    visited[x][y] = true;
                    if (heightMap[x][y] < mx) res += mx - heightMap[x][y];
                    q.push({heightMap[x][y], x * N + y});
                }
            }
        }
        return res;
    }
};
// @lc code=end