---
title: leetcode 407
tags: leetcode, priority queue
---

// https://leetcode.com/problems/trapping-rain-water-ii/
using pii = pair<int, int>;

struct Node {
    int value;
    int x, y;
};

const int go[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
private:
    int n, m;
    bool check(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        n = heightMap.size();
        if (n <= 2) return 0;
        m = heightMap[0].size();
        if (m <= 2) return 0;
        bool visit[110][110] = {false};
        
        auto cmp = [](Node left, Node right) {
            return left.value > right.value;
        };
        priority_queue<Node, vector<Node>, decltype(cmp)> q(cmp);
        for (int i=0; i<m; i++) {
            q.push({heightMap[0][i], 0, i});
            q.push({heightMap[n-1][i], n-1, i});
            visit[0][i] = true;
            visit[n-1][i] = true;
        }
        for (int i=0; i<n; i++) {
            q.push({heightMap[i][0], i, 0});
            q.push({heightMap[i][m-1], i, m-1});
            visit[i][0] = true;
            visit[i][m-1] = true;
        }
        int ans = 0;
        while (q.size()) {
            Node now = q.top();
            q.pop();
            int x = now.x;
            int y = now.y;
            int value = now.value;
            for (int i=0; i<4; i++) {
                int xx = x + go[i][0];
                int yy = y + go[i][1];
                if (check(xx, yy) && !visit[xx][yy]) {
                    if (heightMap[xx][yy] < value) {
                        ans += value - heightMap[xx][yy];
                        q.push({value, xx, yy});
                    } else {
                        q.push({heightMap[xx][yy], xx, yy});
                    }
                    visit[xx][yy] = true;
                }
            }
        }
        return ans;
   }
};