Java solution using PriorityQueue
Source code from:\nhttps://github.com/shawnfan/LintCode/blob/master/Java/Trapping%20Rain%20Water%20II.java\n\n\n\npublic class Solution {\n\n    public class Ce
Source code from:\nhttps://github.com/shawnfan/LintCode/blob/master/Java/Trapping%20Rain%20Water%20II.java\n\n```\n\npublic class Solution {\n\n    public class Cell {\n        int row;\n        int col;\n        int height;\n        public Cell(int row, int col, int height) {\n            this.row = row;\n            this.col = col;\n            this.height = height;\n        }\n    }\n\n    public int trapRainWater(int[][] heights) {\n        if (heights == null || heights.length == 0 || heights[0].length == 0)\n            return 0;\n\n        PriorityQueue<Cell> queue = new PriorityQueue<>(1, new Comparator<Cell>(){\n            public int compare(Cell a, Cell b) {\n                return a.height - b.height;\n            }\n        });\n        \n        int m = heights.length;\n        int n = heights[0].length;\n        boolean[][] visited = new boolean[m][n];\n\n        // Initially, add all the Cells which are on borders to the queue.\n        for (int i = 0; i < m; i++) {\n            visited[i][0] = true;\n            visited[i][n - 1] = true;\n            queue.offer(new Cell(i, 0, heights[i][0]));\n            queue.offer(new Cell(i, n - 1, heights[i][n - 1]));\n        }\n\n        for (int i = 0; i < n; i++) {\n            visited[0][i] = true;\n            visited[m - 1][i] = true;\n            queue.offer(new Cell(0, i, heights[0][i]));\n            queue.offer(new Cell(m - 1, i, heights[m - 1][i]));\n        }\n\n        // from the borders, pick the shortest cell visited and check its neighbors:\n        // if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped\n       // add all its neighbors to the queue.\n        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n        int res = 0;\n        while (!queue.isEmpty()) {\n            Cell cell = queue.poll();\n            for (int[] dir : dirs) {\n                int row = cell.row + dir[0];\n                int col = cell.col + dir[1];\n                if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col]) {\n                    visited[row][col] = true;\n                    res += Math.max(0, cell.height - heights[row][col]);\n                    queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height)));\n                }\n            }\n        }\n        \n        return res;\n    }\n}\n```
[]