407. Trapping Rain Water II

感觉这道题还是比较tricky的，回头再多看看
一个很大的bug是当当前的nextHeight比curr.height小的时候， 同样也需要把curr.height作为当前neighbor点的height加入到pq中，而且也要把当前点标记为visited，才能保证水平面是平的

class Cell {
    public int x;
    public int y;
    public int height;
    public Cell(int x, int y, int height) {
        this.x = x;
        this.y = y;
        this.height = height;
    }
}
public class Solution {
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    public int trapRainWater(int[][] heights) {
        // write your code here
        if (heights == null || heights.length == 0 || heights[0] == null || heights[0].length == 0) return 0;
        int rows = heights.length;
        int cols = heights[0].length;
        PriorityQueue<Cell> pq = new PriorityQueue<>(rows, new Comparator<Cell>() {
            public int compare(Cell a, Cell b) {
                return a.height - b.height;
            }
        });
        for (int i = 0; i < rows; i++) {
            pq.offer(new Cell(i, 0, heights[i][0]));
            heights[i][0] = -1;
            pq.offer(new Cell(i, cols - 1, heights[i][cols - 1]));
            heights[i][cols - 1] = -1;
        }
        for (int i = 1; i < cols - 1; i++) {
            pq.offer(new Cell(0, i, heights[0][i]));
            heights[0][i] = -1;
            pq.offer(new Cell(rows - 1, i, heights[rows - 1][i]));
            heights[rows - 1][i] = -1;
        }
        Cell curr;
        int sum = 0;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        while (!pq.isEmpty()) {
            curr = pq.poll();
            for (int i = 0; i < 4; i++) {
                int x = curr.x + dx[i];
                int y = curr.y + dy[i];
                if (!isValid(rows, cols, x, y)) continue;
                int nextHeight = heights[x][y];
                if (nextHeight == -1) continue;
                if (nextHeight < curr.height) {
                    sum += curr.height - nextHeight;
                }
                //This is the most import part of this algorithm
                //After filled in some water, the level of the current bar is possible been raised, so we need to use the new water height to substitute the original height
                pq.offer(new Cell(x, y, Math.max(curr.height, nextHeight)));
                //System.out.println(curr.height + " " + x + " " + y + " " + sum);
                heights[x][y] = -1;
            }
        }
        return sum;
    }
    private boolean isValid(int rows, int cols, int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
};