1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static class Box {
private final int i;
private final int j;
private final int height;
public Box(int i, int j, int height) {
this.i = i;
this.j = j;
this.height = height;
}
}
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length;
Queue<Box> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.height));
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
Box leftBox = new Box(i, 0, heightMap[i][0]);
Box rightBox = new Box(i, n - 1, heightMap[i][n - 1]);
visited[i][0] = visited[i][n - 1] = true;
queue.offer(leftBox);
queue.offer(rightBox);
}
for (int j = 1; j < n - 1; j++) {
Box topBox = new Box(0, j, heightMap[0][j]);
Box bottomBox = new Box(m - 1, j, heightMap[m - 1][j]);
visited[0][j] = visited[m - 1][j] = true;
queue.offer(topBox);
queue.offer(bottomBox);
}
int water = 0;
while (!queue.isEmpty()) {
Box box = queue.poll();
for (int[] direction : DIRECTIONS) {
int nextI = box.i + direction[0];
int nextJ = box.j + direction[1];
if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && !visited[nextI][nextJ]) {
if (heightMap[nextI][nextJ] < box.height) {
water += box.height - heightMap[nextI][nextJ];
}
visited[nextI][nextJ] = true;
queue.offer(new Box(nextI, nextJ, Math.max(box.height, heightMap[nextI][nextJ])));
}
}
}
return water;
}
}
|