95 lines
2.5 KiB
Java
95 lines
2.5 KiB
Java
/*
|
|
* @lc app=leetcode id=407 lang=java
|
|
*
|
|
* [407] Trapping Rain Water II
|
|
*/
|
|
|
|
// @lc code=start
|
|
class Solution {
|
|
public int trapRainWater(int[][] heightMap) {
|
|
PriorityQueue<Node> pq = new PriorityQueue<>((a, b)->{
|
|
return a.h - b.h;
|
|
});
|
|
boolean[][] visited = visited(heightMap);
|
|
pushBorders(heightMap, visited, pq);
|
|
int[][] dirs = new int[][] {
|
|
new int[] {1, 0},
|
|
new int[] {-1, 0},
|
|
new int[] {0, 1},
|
|
new int[] {0,-1}
|
|
};
|
|
int cap = 0;
|
|
while(!pq.isEmpty()) {
|
|
Node cur = pq.poll();
|
|
int x, y;
|
|
for(int i=0; i<dirs.length; i++) {
|
|
x = cur.r + dirs[i][0];
|
|
y = cur.c + dirs[i][1];
|
|
if(x >= 0 && x < heightMap.length && y >= 0 && y < heightMap[0].length && !visited[x][y]) {
|
|
visited[x][y] = true;
|
|
int curh = heightMap[x][y];
|
|
if(heightMap[x][y] < cur.h) {
|
|
cap += cur.h - heightMap[x][y];
|
|
curh = cur.h;
|
|
}
|
|
pq.add(new Node(x, y, curh));
|
|
}
|
|
}
|
|
}
|
|
return cap;
|
|
}
|
|
|
|
|
|
private void pushBorders(int[][] hm, boolean[][] visited, PriorityQueue<Node> pq) {
|
|
int r = hm.length, c = hm[0].length;
|
|
for(int i=0;i<r;i++) {
|
|
visited[i][0] = true;
|
|
visited[i][c-1] = true;
|
|
pq.add(new Node(i, 0, hm[i][0]));
|
|
pq.add(new Node(i, c-1, hm[i][c-1]));
|
|
}
|
|
for(int i=0;i<c;i++) {
|
|
if(!visited[0][i]) {
|
|
visited[0][i] = true;
|
|
pq.add(new Node(0, i, hm[0][i]));
|
|
}
|
|
if(!visited[r-1][i]) {
|
|
visited[r-1][i] = true;
|
|
pq.add(new Node(r-1, i, hm[r-1][i]));
|
|
}
|
|
}
|
|
}
|
|
|
|
private boolean[][] visited(int[][] heightMap) {
|
|
boolean[][] v = new boolean[heightMap.length][heightMap[0].length];
|
|
for(int i=0; i<v.length; i++) {
|
|
for(int j=0;j<v[0].length;j++) {
|
|
v[i][j] = false;
|
|
}
|
|
}
|
|
return v;
|
|
}
|
|
|
|
static class Node {
|
|
int r, c, h;
|
|
|
|
public Node(int r, int c, int h) {
|
|
this.r = r;
|
|
this.c = c;
|
|
this.h = h;
|
|
}
|
|
}
|
|
}
|
|
// @lc code=end
|
|
|
|
// 12 13 1 12
|
|
// 13 4 13 12
|
|
// 13 8 10 12
|
|
// 12 13 12 12
|
|
// 13 13 13 13
|
|
|
|
// 0 0 0 0
|
|
// 0 9 0 0
|
|
// 0 4 2 0
|
|
// 0 0 0 0
|
|
// 0 0 0 0 |