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来做相邻搜索。
将上下左右四条边加入pq,用一个2维数组来记录每个点是否为边缘。
取pq堆顶元素(最小元素),探索该元素上下左右四个方向元素(在数组范围内且不是边缘),若其相邻元素比当前元素小将其差值计入总数,然后将相邻元素加入pq,并标记为边缘;若其相邻元素比当前元素大,则直接加入pq,并标记为边缘。
直到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;
}
};