Trapping Rain Water II 364

Question

Given n 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

Given 5*4 matrix

[12,13,0,12]

[13,4,13,12]

[13,8,10,12]

[12,13,12,12]

[13,13,13,13]

return 14.

Solution

这道题和Trapping Rain Water类似，也是由边缘最低处开始逐渐向内部灌水。用一个pq来保存当前边缘元素。

tips：用dx，dy来做相邻搜索。

1. 将上下左右四条边加入pq，用一个2维数组来记录每个点是否为边缘。

2. 取pq堆顶元素（最小元素），探索该元素上下左右四个方向元素（在数组范围内且不是边缘），若其相邻元素比当前元素小将其差值计入总数，然后将相邻元素加入pq，并标记为边缘；若其相邻元素比当前元素大，则直接加入pq，并标记为边缘。

3. 直到pq中没有元素为止

代码如下：

public class Solution {
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    class Node{
        int x;
        int y;
        int height;
        public Node(int x, int y, int height){
            this.x = x;
            this.y = y;
            this.height = height;
        }
    }

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    public int trapRainWater(int[][] heights) {
        // write your code here
        if(heights == null || heights.length <= 2 || heights[0].length <= 2){
            return 0;
        }

        int n = heights.length;
        int m = heights[0].length;
        boolean[][] isVisited = new boolean[n][m];

        Queue<Node> queue = new PriorityQueue<Node>(1, new Comparator<Node>(){
            public int compare(Node a, Node b){
                return a.height - b.height;
            }
        });
        //add first and last column
        for(int i = 0; i < n; i++){
            queue.offer(new Node(i, 0, heights[i][0]));
            isVisited[i][0] = true;
            queue.offer(new Node(i, m - 1, heights[i][m - 1]));
            isVisited[i][m - 1] = true;
        }
        //add first and last row
        for(int j = 1; j < m - 1; j++){
            queue.offer(new Node(0, j, heights[0][j]));
            isVisited[0][j] = true;
            queue.offer(new Node(n - 1, j, heights[n - 1][j]));
            isVisited[n - 1][j] = true;
        }

        int sum = 0;
        while(!queue.isEmpty()){
            Node curt = queue.poll();
            for(int i = 0; i < 4; i++){
                int nextX = curt.x + dx[i];
                int nextY = curt.y + dy[i];
                if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && !isVisited[nextX][nextY]){
                    if(heights[nextX][nextY] < curt.height){
                        sum += curt.height - heights[nextX][nextY];
                        queue.offer(new Node(nextX, nextY, curt.height));
                        isVisited[nextX][nextY] = true;
                    }else{
                        queue.offer(new Node(nextX, nextY, heights[nextX][nextY]));
                        isVisited[nextX][nextY] = true;
                    }
                }
            }
        }

        return sum;
    }
};