# 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.

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

Related Problems

Medium Trapping Rain Water

## Analysis

1. 从最外围一圈向内部遍历，记录包围“墙”的最小柱高，可以利用min-heap（PriorityQueue）
2. 记录遍历过的点`visited[][]`
3. 对于min-heap的堆顶元素，假设高度`h`，查找其周围4个方向上未曾访问过的点
• 如果比`h`高，则说明不能装水，但是提高了“围墙”最低高度，因此将其加入min-heap中，设置元素被访问
• 如果比`h`矮，则说明可以向其中灌水，且灌水高度就是`h - h'`，其中`h'`是当前访问的柱子高度，同样的，要将其加入min heap中，（且该元素高度记为灌水后的高度，也就是`h`，可以设想为一个虚拟的水位高度），设置元素被访问

## 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;
}
}
``````