Java solution beating 100%
My method is still based on PriorityQueue(heap). But it is combined with flood fill.\nMaintain a heap which contains the current walls, the boundary of the wate
My method is still based on PriorityQueue(heap). But it is combined with flood fill.\nMaintain a heap which contains the current walls, the boundary of the water pool.\nEvery time we pick the lowest wall as a bar, then recursively travel from this wall to its neighbors to find if they can trap the water.\nIf we meet a position which is lower than the bar, we trap some water, else we meet a new wall and put it into the heap.\nWe can use a 2-D array to memorize the visited position and a member variable to records the water we have trapped.\n```\npublic class Solution {\n    private static class Cell implements Comparable<Cell> {\n        private int row;\n        private int col;\n        private int value;\n        public Cell(int r, int c, int v) {\n            this.row = r;\n            this.col = c;\n            this.value = v;\n        }\n        @Override\n        public int compareTo(Cell other) {\n            return value - other.value;\n        }\n    }\n    private int water;\n    private boolean[][] visited1;\n    public int trapRainWater(int[][] heightMap) {\n        if (heightMap.length == 0) return 0;\n        PriorityQueue<Cell> walls = new PriorityQueue<Cell>();\n        water = 0;\n        visited1 = new boolean[heightMap.length][heightMap[0].length];\n        int rows = heightMap.length, cols = heightMap[0].length;\n        //build wall;\n        for (int c = 0; c < cols; c++) {\n        \twalls.add(new Cell(0, c, heightMap[0][c]));\n        \twalls.add(new Cell(rows - 1, c, heightMap[rows - 1][c]));\n        \tvisited1[0][c] = true;\n        \tvisited1[rows - 1][c] = true;\n        }\n        for (int r = 1; r < rows - 1; r++) {\n        \twalls.add(new Cell(r, 0, heightMap[r][0]));\n        \twalls.add(new Cell(r, cols - 1, heightMap[r][cols - 1]));\n        \tvisited1[r][0] = true;\n        \tvisited1[r][cols - 1] = true;\n        }\n        //end build wall;\n        while(walls.size() > 0) {\n            Cell min = walls.poll();\n            visit(heightMap, min, walls);\n        }\n        return water;\n    }\n    private void visit(int[][] height, Cell start, PriorityQueue<Cell> walls) {\n        fill(height, start.row + 1, start.col, walls, start.value);\n        fill(height, start.row - 1, start.col, walls, start.value);\n        fill(height, start.row, start.col + 1, walls, start.value);\n        fill(height, start.row, start.col - 1, walls, start.value);\n    }\n    private void fill(int[][] height, int row, int col, PriorityQueue<Cell> walls, int min) {\n        if (row < 0 || col < 0) return;\n        else if (row >= height.length || col >= height[0].length) return;\n        else if (visited1[row][col]) return;\n        else if (height[row][col] >= min) {\n            walls.add(new Cell(row, col, height[row][col]));\n            visited1[row][col] = true;\n            return;\n        } else {\n//        \tSystem.out.println(row + ", " + col + " height = " + height[row][col] + ", bar = " + min);\n            water += min - height[row][col];\n            visited1[row][col] = true;\n            fill(height, row + 1, col, walls, min);\n            fill(height, row - 1, col, walls, min);\n            fill(height, row, col + 1, walls, min);\n            fill(height, row, col - 1, walls, min);\n        }\n    }\n}\n```
[]