1
const dir = [
2
  [0, -1],
3
  [-1, 0],
4
  [0, 1],
5
  [1, 0],
6
];
7
const MAX = 200 * 201; // n * m + m
8
const trapRainWater = (g) => {
9
  let n = g.length,
10
    m = g[0].length;
11
  if (n == 0) return 0;
12
  let res = 0,
13
    max = Number.MIN_SAFE_INTEGER;
14
  let pq = new MinPriorityQueue({ priority: (x) => x[0] * MAX + x[1] }); // first priority: x[0], smaller comes first. second priority: x[1], smaller comes first
15
  let visit = initialize2DArrayNew(n, m);
16
  for (let i = 0; i < n; i++) {
17
    for (let j = 0; j < m; j++) {
18
      if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
19
        pq.enqueue([g[i][j], i * m + j]);
20
        visit[i][j] = true;
21
      }
22
    }
23
  }
24
  while (pq.size()) {
25
    // BFS
26
    let cur = pq.dequeue().element;
27
    let h = cur[0],
28
      r = (cur[1] / m) >> 0,
29
      c = cur[1] % m; // height row column
30
    max = Math.max(max, h);
31
    for (let k = 0; k < 4; k++) {
32
      let x = r + dir[k][0],
33
        y = c + dir[k][1];
34
      if (x < 0 || x >= n || y < 0 || y >= m || visit[x][y]) continue;
35
      visit[x][y] = true;
36
      if (g[x][y] < max) res += max - g[x][y];
37
      pq.enqueue([g[x][y], x * m + y]);
38
    }
39
  }
40
  return res;
41
};
42

43
const initialize2DArrayNew = (n, m) => {
44
  let data = [];
45
  for (let i = 0; i < n; i++) {
46
    let tmp = Array(m).fill(false);
47
    data.push(tmp);
48
  }
49
  return data;
50
};