Trapping Rain Water II

Givenn_x_m_non-negative integers representing an elevation map 2d where the area of each cell is_1_x_1, compute how much water it is able to trap after raining.

Example

Given5*4matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]

return14.

Solution: The thought is like trapping water1, always from the lowest to highest. We can use a min heap to do this.

class Node {
    int x;
    int y;
    int val;
    public Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}
class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n1, Node n2) {
        return n1.val - n2.val;
    }
}
public int trapRainWater(int[][] heights) {
    if(heights == null || heights.length == 0) {
        return 0;
    }
    int[] dx = new int[]{1, 0, -1, 0};
    int[] dy = new int[]{0, 1, 0, -1};
    int m = heights.length, n = heights[0].length;
    int res = 0;
    PriorityQueue<Node> minHeap = new PriorityQueue<Node>(2 * (m + n), new NodeComparator());
    boolean[][] visited = new boolean[m][n];
    for(int i = 0; i < m; i++) {
        minHeap.offer(new Node(i, 0, heights[i][0]));
        minHeap.offer(new Node(i, n - 1, heights[i][n - 1]));
        visited[i][0] = true;
        visited[i][n - 1] = true;
    }
    for(int i = 0; i < n; i++) {
        minHeap.offer(new Node(0, i, heights[0][i]));
        minHeap.offer(new Node(m - 1, i, heights[m - 1][i]));
        visited[0][i] = true;
        visited[m - 1][i] = true;
    }
    while(!minHeap.isEmpty()) {
        Node tmp = minHeap.poll();
        for(int j = 0; j < 4; j++) {
            int nx = tmp.x + dx[j];
            int ny = tmp.y + dy[j];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                minHeap.offer(new Node(nx, ny, Math.max(heights[nx][ny], tmp.val)));
                visited[nx][ny] = true;
                res += Math.max(0, tmp.val - heights[nx][ny]);
            }
        }
    }
    return res;
}