往高低不平的一堆相连的方柱注水，问最多能保持住多少水。是之前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