Trapping Rain Water II

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.

Trapping Rain Water II

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.

Tags

LintCode Copyright Heap Matrix

Related Problems

Medium Trapping Rain Water

Analysis

本题是Trapping Rain Water的follow up，I中是循环两遍记录每个位置左右两侧的最高水柱，而II在二维的灌水情境中，则需要从外围向内包围查找，记录最小的柱高，也就是木桶原理，最矮的柱子决定了灌水的高度。

1. 从最外围一圈向内部遍历，记录包围“墙”的最小柱高，可以利用min-heap（PriorityQueue）

2. 记录遍历过的点visited[][]

3. 对于min-heap的堆顶元素，假设高度h，查找其周围4个方向上未曾访问过的点

   • 如果比h高，则说明不能装水，但是提高了“围墙”最低高度，因此将其加入min-heap中，设置元素被访问

   • 如果比h矮，则说明可以向其中灌水，且灌水高度就是h - h'，其中h'是当前访问的柱子高度，同样的，要将其加入min heap中，（且该元素高度记为灌水后的高度，也就是h，可以设想为一个虚拟的水位高度），设置元素被访问

此外，为了方便，可以定义一个Cell类，包含其坐标x,y，以及高度h，并定义其Comparator规则（也可以在初始化PriorityQueue的时候定义）。

Solution

class Cell {
    public int x, y, h;

    public Cell() {}

    public Cell(int x, int y, int h) {
        this.x = x;
        this.y = y;
        this.h = h;
    }
}

public class Solution {
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    public int trapRainWater(int[][] heights) {
        // Input validation
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return 0;
        }

        int m = heights.length;
        int n = heights[0].length;

        // Initialize min-heap minheap, visited matrix visited[][]
        PriorityQueue<Cell> minheap = new PriorityQueue<Cell>(1, new Comparator<Cell>() {
            public int compare(Cell c1, Cell c2) {
                if (c1.h > c2.h) {
                    return 1;
                } else if (c1.h < c2.h) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        int[][] visited = new int[m][n];

        // Traverse the outer cells, add to the minheap
        for (int i = 0; i < m; i++) {
            minheap.offer(new Cell(i, 0, heights[i][0]));
            minheap.offer(new Cell(i, n - 1, heights[i][n - 1]));

            visited[i][0] = 1;
            visited[i][n - 1] = 1;
        }

        for (int j = 0; j < n; j++) {
            minheap.offer(new Cell(0, j, heights[0][j]));
            minheap.offer(new Cell(m - 1, j, heights[m - 1][j]));

            visited[0][j] = 1;
            visited[m - 1][j] = 1;
        }

        // Helper direction array
        int[] dirX = new int[] {0, 0, -1, 1};
        int[] dirY = new int[] {-1, 1, 0, 0};

        int water = 0;

        // Starting from the min height cell, check 4 direction
        while (!minheap.isEmpty()) {
            Cell now = minheap.poll();

            for (int k = 0; k < 4; k ++) {
                int x = now.x + dirX[k];
                int y = now.y + dirY[k];

                if (x < m && x >= 0 && y < n && y >= 0 && visited[x][y] != 1) {
                    minheap.offer(new Cell(x, y, Math.max(now.h, heights[x][y])));
                    visited[x][y] = 1;

                    // Fill in water or not
                    water += Math.max(0, now.h - heights[x][y]);
                }
            }
        }
        return water;
    }
}

Reference

• Jason_Yuan: LintCode 364