Trapping Rain Water 2

二维向内灌水，需要用到heap，比较找出最小的“柱子”

code

class slot {
public:
    int x;
    int y;
    int val;
    slot(int x, int y, int val)
    {
        this->x = x;
        this->y = y;
        this->val = val;
    }

    bool operator < (const slot& s1) const
    {
        return this->val > s1.val;
    }
};

class Solution {
public:
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    int trapRainWater(vector<vector<int> > &heights) {
        // write your code here
        if(heights.size() == 0 || heights[0].size() == 0)
        {
            return 0;
        }

        int m = heights.size();
        int n = heights[0].size();

        priority_queue<slot> heap;
        int sum = 0;
        vector<vector<bool>> flag;

        // set default flag
        for(int i = 0; i < m; i++)
        {
            vector<bool> tmp(n, false);
            flag.push_back(tmp);
        }

        // first row and last row
        for(int i = 0; i<n; i++)
        {
            heap.push(slot(0, i, heights[0][i]));
            flag[0][i] = true;
            heap.push(slot(m-1, i, heights[m-1][i]));
            flag[m-1][i] = true;
        }

        // first col and last col
        for(int i = 0; i < m; i++)
        {
            heap.push(slot(i, 0, heights[i][0]));
            flag[i][0] = true;
            heap.push(slot(i, n-1, heights[i][n-1]));
            flag[i][n-1] = true;
        }

        int dx[] = {1, 0, -1, 0};
        int dy[] = {0, 1, 0, -1};

        while(!heap.empty())
        {
            slot s = heap.top();
            heap.pop();

            for(int i = 0; i<4; i++)
            {
                int nx = s.x + dx[i];
                int ny = s.y + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n || flag[nx][ny] == true)
                {
                    continue;
                }

                flag[nx][ny] = true;
                heap.push(slot(nx, ny, max(s.val, heights[nx][ny])));
                sum += max(0, s.val-heights[nx][ny]);
            }
        }

        return sum;

    }
};