Trapping Rain Water II

Problem:

it is able to trap after raining.

Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

Analysis:

1. Add all border cells to priority queue

2. BFS from pq, if  adjacent cell's height is lower than current cell, fill the water and enqueue with filled hight.

Solution: 

class Solution {
    class Cell {
        int h;
        int r;
        int c;
        Cell(int h, int r, int c) {
            this.h = h;
            this.r = r;
            this.c = c;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0)
            return 0;

        PriorityQueue<Cell> queue = new PriorityQueue<>(110*110, new Comparator<Cell>(){
            public int compare(Cell p1, Cell p2) {
                return p1.h - p2.h;
            }
        });
        int m = heightMap.length;
        int n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        int res = 0;

        for (int i = 0; i < m; i++) {
            queue.offer(new Cell(heightMap[i][0], i, 0));
            queue.offer(new Cell(heightMap[i][n - 1], i, n - 1));
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }

        for (int i = 0; i < n; i++) {
            queue.offer(new Cell(heightMap[0][i], 0, i));
            queue.offer(new Cell(heightMap[m - 1][i], m - 1, i));
            visited[0][i] = true;
            visited[m - 1][i] = true;
        }
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            Cell cur = queue.poll();
            for (int[] dir: dirs) {
                int newr = cur.r + dir[0];
                int newc = cur.c + dir[1];
                if (newr >= 0 && newr < m && newc >= 0 && newc < n && !visited[newr][newc]) {
                    res += Math.max(0, cur.h - heightMap[newr][newc]);
                    visited[newr][newc] = true;
                    queue.offer(new Cell(Math.max(cur.h, heightMap[newr][newc]), newr, newc)); 
                }
            }   
        }


        return res;
    }

    
}