# 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](/files/-M63nPA0e2qKVi8IJzas)

**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

```java
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](http://www.jianshu.com/p/540ee7ec725b)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/heap/trapping_rain_water_ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.