1
class Solution {
2
  public class pair implements Comparable<pair> {
3
    int row;
4
    int col;
5
    int val;
6

7
    pair(int row, int col, int val) {
8
      this.row = row;
9
      this.col = col;
10
      this.val = val;
11
    }
12

13
    public int compareTo(pair o) {
14
      return this.val - o.val;
15
    }
16
  }
17

18
  int[][] dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
19

20
  public int trapRainWater(int[][] heightMap) {
21
    int n = heightMap.length;
22
    int m = heightMap[0].length;
23

24
    PriorityQueue<pair> pq = new PriorityQueue<>();
25

26
    boolean[][] visited = new boolean[n][m];
27

28
    // add all the boundary elements in pq
29

30
    for (int i = 0; i < n; i++) {
31
      for (int j = 0; j < m; j++) {
32
        if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
33
          pq.add(new pair(i, j, heightMap[i][j]));
34
          visited[i][j] = true;
35
        }
36
      }
37
    }
38

39
    int ans = 0;
40

41
    while (pq.size() > 0) {
42
      pair rem = pq.remove();
43
      for (int i = 0; i < 4; i++) {
44

45
        int rowdash = rem.row + dir[i][0];
46
        int coldash = rem.col + dir[i][1];
47

48
        if (rowdash >= 0
49
            && coldash >= 0
50
            && rowdash < n
51
            && coldash < m
52
            && visited[rowdash][coldash] == false) {
53
          visited[rowdash][coldash] = true;
54
          if (heightMap[rowdash][coldash] >= rem.val) {
55
            pq.add(new pair(rowdash, coldash, heightMap[rowdash][coldash])); // boundary is updated
56
          } else {
57
            int waterstored = rem.val - heightMap[rowdash][coldash];
58
            ans += waterstored; // now this will act as a wall add in pq
59
            pq.add(new pair(rowdash, coldash, heightMap[rowdash][coldash] + waterstored));
60
          }
61
        }
62
      }
63
    }
64
    return ans;
65
  }
66
}