leetcode 407. 接雨水 II

题目：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;
    }
};