1
class Solution {
2
 public:
3
  bool vis[201][201]; // to keep track of visited cell
4
  int n, m;
5
  bool isValid(int i, int j) {
6
    if (i < 0 || i >= m || j < 0 || j >= n || vis[i][j] == true) return false;
7

8
    return true;
9
  }
10
  int trapRainWater(vector<vector<int>> &heightMap) {
11
    vector<vector<int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // direction Vector
12
    m = heightMap.size();
13
    if (m == 0) return 0; // m=0 is one edge case
14
    n = heightMap[0].size();
15
    memset(vis, false, sizeof(vis));
16
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
17
                   greater<pair<int, pair<int, int>>>>
18
        pq; // min heap w.r.t cell height
19
    for (int i = 0; i < m; i++) {
20
      for (int j = 0; j < n; j++) {
21
        if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
22
          pq.push({heightMap[i][j], {i, j}}); // pushing all outer cells in pq
23
          vis[i][j] = true;
24
        }
25
      }
26
    }
27
    int water = 0;
28
    int Height = INT_MIN;
29
    while (!pq.empty()) { // normal BFS
30
      auto pr = pq.top();
31
      pq.pop();
32
      int height = pr.first;
33
      int i = pr.second.first;
34
      int j = pr.second.second;
35
      Height = max(Height, height);
36
      for (int d = 0; d < 4; d++) { // iterating through direction vector
37
        int x = i + dir[d][0];
38
        int y = j + dir[d][1];
39
        if (isValid(x, y)) {
40
          water += max(0, Height - heightMap[x][y]); // just adding the diff between cell
41
                                                     // height and surrounding height
42
          vis[x][y] = true;
43
          pq.push({heightMap[x][y], {x, y}});
44
        }
45
      }
46
    }
47
    return water;
48
  }
49
};