题目：407. 接雨水 II - 力扣（LeetCode）

堆+bfs。

模拟水流出去的过程。先把边缘的单元都加到堆里，从堆顶最小的单元开始bfs，遍历到的单元的四周，都会从该单元流出去，四周的单元的剩余水量+高度=max(自己的高度，遍历到单元的水量)

struct Node {int x, y;int h;int w;bool v = false;Node(int x, int y, int h) {this->x = x;this->y = y;this->h = h;w = 30000;}
};
bool myComp(Node* a, Node* b) {return a->h < b->h;
}
class Solution {
public:int trapRainWater(vector<vector<int>>& heightMap) {int n = heightMap.size();int m = heightMap[0].size();vector<vector<Node*>> f;vector<Node*> heap;for (int i = 0; i < n; i++) {vector<Node*> t(m);for (int j = 0; j < m; j++) {t[j] = new Node(i, j, heightMap[i][j]);if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {heap.push_back(t[j]);t[j]->w = t[j]->h;t[j]->v = true;}}f.push_back(t);}sort(heap.begin(), heap.end(), myComp);Node* node;Node* t;while (!heap.empty()) {node = heap[0];if (node->x > 0) {t = f[node->x - 1][node->y];if (!t->v) {t->v = true;t->w = max(t->h, node->w);heap.push_back(t);int idx = HeapUp(heap, heap.size() - 1);HeapDown(heap, idx);}}if (node->x < n - 1) {t = f[node->x + 1][node->y];if (!t->v) {t->v = true;t->w = max(t->h, node->w);heap.push_back(t);int idx = HeapUp(heap, heap.size() - 1);HeapDown(heap, idx);}}if (node->y > 0) {t = f[node->x][node->y - 1];if (!t->v) {t->v = true;t->w = max(t->h, node->w);heap.push_back(t);int idx = HeapUp(heap, heap.size() - 1);HeapDown(heap, idx);}}if (node->y < m - 1) {t = f[node->x][node->y + 1];if (!t->v) {t->v = true;t->w = max(t->h, node->w);heap.push_back(t);int idx = HeapUp(heap, heap.size() - 1);HeapDown(heap, idx);}}heap[0] = heap[heap.size() - 1];heap.pop_back();HeapDown(heap, 0);}int ret = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret += f[i][j]->w - f[i][j]->h;
//                printf("%d ", f[i][j]->w - f[i][j]->h);}
//            printf("\n");}return ret;}int HeapUp(vector<Node*>& heap, int idx) {if (idx == 0) {return idx;}int tmp = (idx - 1) / 2;Node* t = heap[tmp];if (t->w > heap[idx]->w) {heap[tmp] = heap[idx];heap[idx] = t;return HeapUp(heap, tmp);}return idx;}int HeapDown(vector<Node*>& heap, int idx) {int tmp = -1;if (idx * 2 + 1 < heap.size()) {tmp = idx * 2 + 1;if (tmp + 1 < heap.size()) {if (heap[tmp + 1]->w < heap[tmp]->w) {tmp++;}}}if (tmp >= 0 && heap[idx]->w > heap[tmp]->w) {Node* t = heap[idx];heap[idx] = heap[tmp];heap[tmp] = t;return HeapDown(heap, tmp);}return idx;}
};