Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.
Example 1:
**Input:** heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
**Output:** 4
**Explanation:** After the rain, water is trapped between the blocks.
We have two small pounds 1 and 3 units trapped.
The total volume of water trapped is 4.
class Solution {
public int trapRainWater(int[][] heightMap) {
// edge cases
if (heightMap.length <= 2 || heightMap[0].length <= 2) return 0;
int[][] dirs = new int[][]{{0,1},{0,-1},{1,0}, {-1,0}};
int row = heightMap.length, col = heightMap[0].length;
boolean[][] visited = new boolean[row][col];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {return heightMap[a[0]][a[1]] - heightMap[b[0]][b[1]];});
// priority queue, get smallest. start from boarder
for (int c = 0; c < col; c++) {
pq.offer(new int[]{0, c}); visited[0][c] = true;
pq.offer(new int[]{row-1, c}); visited[row-1][c] = true;
}
for (int r = 1; r < row-1; r++) {
pq.offer(new int[]{r, 0}); visited[r][0] = true;
pq.offer(new int[]{r, col-1});visited[r][col-1] = true;
}
// each time process smallest one
int sum = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int min = heightMap[curr[0]][curr[1]];
Queue<int[]> q = new LinkedList<>();
q.offer(curr);
while (!q.isEmpty()) {
int[] curr2 = q.poll();
// 4 directions
for (int[] d : dirs) {
int r = curr2[0] + d[0];
int c = curr2[1] + d[1];
if (r < 0 || r >= row || c < 0 || c >= col || visited[r][c]) continue; // out of boundary or visited
if (heightMap[r][c] <= min) { // add to sum, add to queue
sum += min - heightMap[r][c];
q.offer(new int[]{r, c});
} else { // greater one, add to pq
pq.offer(new int[]{r, c});
}
visited[r][c] = true; // marked visited
}
}
}
return sum;
}
}
/*
The idea is same with https://leetcode.com/problems/trapping-rain-water/description/
just fron 2D to 3D
start from the edge, move smallest inward, when meet smaller one add to sum
visualization: https://www.youtube.com/watch?v=cJayBq38VYw
1) priority queue, start from boarder. 2) poll smallest one, queue BFS, when meet smaller add to sum / add to queue for next, when meet bigger add to priority queue.
*/
