Trapping Water II

Question quoted from lintcode

Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.

img

Example:

Given 5*4 matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]

return 14.

Idea

這題用母語都不容易把代碼講明白。
題目大意就是要向這些柱子組成的矩陣澆水，問一共能灌多少水。題目假設柱子之間沒有間隙。

我先講講我自己的思路吧。
思路說起來好像挺簡單的，就是從最外層開始澆水，層層往矩陣內部澆。
一圈柱子圍起來，它的可灌水高度，是由最低的一根柱子決定的。直觀上，你要把最外層的圈找到，得到可灌水高度(最低柱)， 然後嘗試向圈內灌水，然後，往圈子內部找下一個更高的封閉圈，往上澆水，再找下一個封閉圈……

實際上代碼直接實現這個思路非常麻煩。把所有的封閉圈辨識出來就夠你喝一壺的。以下介紹另一種思路。非原創，代碼如有類同，實屬抄襲。

代碼實現的思路

我們不考慮可灌水量，因爲每根柱子都不一樣，我們考慮灌水後的高度。這個高度對於每一個柱子圍成的圈來說， 每根內柱都是一樣，統一的，除非柱子超出了水面。

定義一個數據結構Cell, 裏面包含了柱子的位置，和柱子的灌水後高度。

維護一個最小優先隊列，先把矩陣4條邊的柱子和他們的灌水後高度打包成Cell, 全部送進隊列，也就是首行尾行和首列尾列，對於這4條邊來說，每一根柱子的灌水後的高度應該是自身高度 + 0單位的水也就是柱子高度本身，因爲最外層邊柱不能夠被灌水。

然後不停執行隊列的出列操作。

推論1

這裏必須理解的是，由於最外圈已經首先訪問過了，並且全部排進了隊列，所以接下來出列的每一根柱子，還有他們的未訪問的相鄰柱子，都必然在不可能在最外圈以外。只能在最外圈或最外圈以內。

最小優先隊列第一次出列的，必然是邊柱最矮的一根。
檢查其前後左右而且"沒有訪問過"的相鄰柱子，嘗試向其灌水。如果鄰居比它的灌水後高度還矮，那就可以灌水。給鄰居柱子灌水以後，你可以把鄰居看成一條邊柱，它的高度爲“鄰居自身高度 + 灌上去的水”，也就是出列的柱子本身的高度，把這根虛擬的邊柱加進隊列，以便未來會對其鄰居進行灌水。如果鄰居比出列柱子的灌水後高度還要高，那這根柱子已經浮出水面了，把鄰居當作邊柱，直接加進隊列。

所以這裏對於每一根柱子的遍歷順序是這樣的：首先是最外包圍的圈，然後逐漸向內蔓延（前後左右的鄰居柱子）直到把整個矩陣都訪問一遍。

推論2

由於永遠是最矮的柱子先出列，所以可以確定的是，遍歷過程中，圍圈的最低柱子和它的鄰居總是會被最先灌水。

這個灌水的順序和現實物理是相悖的。這裏是理解代碼最困難的地方，一點也不直觀。

Code

class Cell {
    public final int rowNum; 
    public final int colNum;

    // 注意，這裏表示灌水後的高度! 如果這個位置不能被灌水，就會和柱子高度一樣，相當於加了0個單位的水
    public final int waterLevel; 

    Cell(int rowNum, int colNum, int level) {
        this.rowNum = rowNum;
        this.colNum = colNum;
        this.waterLevel = level;
    }
}

public class Solution {
    /*
     * @param heights: a matrix of integers
     * @return: an integer
     */
    public int trapRainWater(int[][] heights) {
        // write your code here
        if (heights.length == 0) return 0;
        
        // 創建一個最小優先隊列，語法挺麻煩的
        PriorityQueue<Cell> boundaryCells = new PriorityQueue<Cell>((c1, c2) -> {
            if (c1.waterLevel == c2.waterLevel) return 0;
            if (c1.waterLevel > c2.waterLevel) return 1;
            return -1;
        });

        int rowLen = heights.length;
        int colLen = heights[0].length;

        // initialize the variable
        boolean[][] visited = new boolean[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                visited[i][j] = false;
            }
        }

        // 把首行，尾行，首列，尾列的柱子都加進隊列
        int firstRow = 0;
        int firstColumn = 0;
        int lastRow = rowLen - 1;
        int lastColumn = colLen - 1;

        // first column and last column 首列尾列
        for(int row_i = 0; row_i < rowLen; row_i++) {
            boundaryCells.add(new Cell(row_i, firstColumn, heights[row_i][firstColumn]));
            boundaryCells.add(new Cell(row_i, lastColumn, heights[row_i][lastColumn]));
            visited[row_i][firstColumn] = true;
            visited[row_i][lastColumn] = true;
        }

        // first row and last row 首行尾行
        for(int column_i = 1; column_i < colLen - 1; column_i++) {
            boundaryCells.add(new Cell(firstRow, column_i, heights[firstRow][column_i]));
            boundaryCells.add(new Cell(lastRow, column_i, heights[lastRow][column_i]));
            visited[firstRow][column_i] = true;
            visited[lastRow][column_i] = true;
        }

        int water = 0;
        int[][] moves = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, };
        int row = 0; int col = 1;
        while(!boundaryCells.isEmpty()) {
            // start from the cell with least waterLevel 出列的順序一定是最矮的先出
            Cell current = boundaryCells.poll();

            // visit its 4 neighbors
            for(int[] move : moves) {
                int rowPos = current.rowNum + move[row];
                int colPos = current.colNum + move[col];

                // make sure the neighbor is valid index
                // and is never visited before
                boolean valid = (0 <= rowPos && rowPos < rowLen) &&
                        (0 <= colPos && colPos < colLen) &&
                        visited[rowPos][colPos] == false;

                if (valid) {
                    visited[rowPos][colPos] = true;
                    if (current.waterLevel > heights[rowPos][colPos]) {
                        water += current.waterLevel - heights[rowPos][colPos];
                        // 這是一根虛擬的邊柱，其高度 = 真實柱子高度 + 灌上的水, 也就是和當前柱子的灌水後高度一樣的
                        boundaryCells.add(new Cell(rowPos, colPos, current.waterLevel));
                    } else {
                        // 這根柱子浮出水面了，有可能成爲下一個"更高的內圈"的邊柱，這根柱子越高，就越排到後面才出列。
                        boundaryCells.add(new Cell(rowPos, colPos, heights[rowPos][colPos]));
                    }
                }
            }
        }
        return water;
    }
}