BFS MinHeap with Explanation
Logical Thinking\nAccording to the Liebig\'s law of the minimum, the lowest border decides how much water trapped at a cell.\n\nIf I can determine that the curr
**Logical Thinking**\nAccording to the [Liebig\'s law of the minimum](http://https://en.wikipedia.org/wiki/Liebig%27s_law_of_the_minimum), the lowest border decides how much water trapped at a cell.\n\nIf I can determine that the current cell is the lowest border of its adjacent cell, we can safely count trapped water.\n\nFor example,\n```\n[\n  [0, 3, 0],\n  [2, 1, 3],\n  [0, 3, 0],\n]\n\nAssuming the current cell is grid[1][0],\nif I am sure grid[1][0] is the lowest border of grid[1][1], \ngrid[1][0] - grid[1][1] water is trapped\n```\n\nHow do we determine whether the current cell is the lowest border cell of its adjacent cell or not?\n\nWe wanted to traverse and update the above grid in the order as follows\n```\n[\n  [1st, 4th, 1st],\n  [2nd, 3rd, 4th],\n  [1st, 4th, 1st],\n]\n\nThat is,\n\ngrid[0][0] \ngrid[2][2] \ngrid[0][2] \ngrid[2][0] \n\ngrid[1][0] : trap 1 water with grid[1][1], update grid[1][1] from 1 to 2\ngrid[1][1] \n\ngrid[1][2] \ngrid[2][1] \ngrid[0][1] \n\n```\nWe can achieve that with the help of a MinHeap `lowestBorderCandidates` which polls the lowest cell in the heap. \nWe add border cells of grid into `lowestBorderCandidates` initially.\n\nFor a cell polled from `lowestBorderCandidates`, we calculate water trapped with its adjacent cells `adj` that has never been added to heap, i.e. `unableTrapWater  = false`. \nIf there is water trapped, we update height of `adj` and add it to `lowestBorderCandidates`. Or else, we add `adj` to `lowestBorderCandidates` directly.\n\nIn this way, we restrict the order of `lowestBorderCandidate x`, and we calculate height difference with its adjcent cell whoes `unableTrapWater` is false.\n****\n```\n    private static final int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n    \n    public int trapRainWater(int[][] heightMap) {\n        // Corner case to add.\n        if (heightMap == null || heightMap.length <= 1)\n            return 0;\n        \n        int rows = heightMap.length, cols = heightMap[0].length;\n        \n        // Init lowestBorderCandidates of cells.\n        PriorityQueue<Cell> lowestBorderCandidates = new PriorityQueue<>((a, b) -> Integer.compare(a.height, b.height));\n        boolean[][] unableTrapWater = new boolean[rows][cols];\n        \n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {\n                    unableTrapWater[i][j] = true;\n                    lowestBorderCandidates.add(new Cell(i, j, heightMap[i][j]));\n                }\n            }\n        }\n        \n        // BFS from border.\n        int waterTrapped = 0;\n        while (!lowestBorderCandidates.isEmpty()) {\n            Cell cell = lowestBorderCandidates.poll();\n            for (int[] direction : directions) {\n                int nx = cell.x + direction[0];\n                int ny = cell.y + direction[1];\n                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !unableTrapWater[nx][ny]) {\n                    unableTrapWater[nx][ny] = true;\n                    if (cell.height > heightMap[nx][ny]) {\n                        waterTrapped += cell.height - heightMap[nx][ny];\n                        lowestBorderCandidates.add(new Cell(nx, ny, cell.height));\n                    } else {\n                        lowestBorderCandidates.add(new Cell(nx, ny, heightMap[nx][ny]));\n                    }\n                }\n            }\n        }\n        \n        return waterTrapped;\n    }\n    \n    class Cell {\n        int x;\n        int y;\n        int height;\n        public Cell(int x, int y, int height) {\n            this.x = x;\n            this.y = y;\n            this.height = height;\n        }\n    }\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]