接雨水（二维）

题目

有一堆摆成矩形的方块，每个方块的高度不同，问这一堆方块能够接下多少雨水
输入：二维数组，表示每个方块的高度
输出：能够接下雨水的体积

思路

由内向外扩展：从最低方块开始，向四周扩展至比它高的方块，再对这些高方块进行相同的操作，直到边界、所有方块被访问；
由外向内包围：从边界的最低方块开始，向四周扩展，寻找比它矮的方块，用雨水填上，直到所有方块都被访问
显然由外向内包围的思路更简单
实现：

1. 定义一个类，包含坐标(row,col)与填上雨水后的高度信息
2. 搜所的过程是从外向内蔓延，因此需要一个集合；每次只考虑集合中最小的元素，则想到用优先队列（堆）来解决

过程：

1. 将矩形四周的元素offer进堆，并标记为已访问
2. poll堆顶元素（最矮的边界），分别考察向上下左右的元素，若元素

代码

类定义

class Cell{
        int row;
        int col;
        int height;
        public Cell(int row, int col, int height){
                this.row = row;
                this.col = col;
                this.height = height;
        }
}

实现代码

public int getRain(int[][] heights){
        if(heights==null || heights.length==0 || heights[0].length==0)
                return 0;
        int m = heights.length;
        int n = heights[0].length;
        //如何将对象组织成优先队列
        PriorityQueue<Cell> queue = new PriorityQueue(new Comparator<Cell>(){
                        public int compare(Cell a,Cell b){
                                return a.height - b.height;
                        }
                });
        //使用visited记录访问情况，而不是看是否存在于优先队列中
        boolean[][] visited = new boolean[m][n];

        for(int i=0;i<m;i++){
                visited[i][0] = true;
                visited[i][m-1] = true;
                queue.offer(new Cell(i,0,heights[i][0]));
                queue.offer(new Cell(i,m-1,heights[i][m-1]));
        }
        for(int j=0;j<n;j++){
                visited[0][j] = true;
                visited[n-1][j] = true;
                queue.offer(new Cell(0,j,heights[0][j]));
                queue.offer(new Cell(n-1,j,heights[n-1][j]));
        }
        //使用方向数组提高可读性
        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
        int total = 0;
        while(!queue.isEmpty()){
                Cell cell = queue.poll();
                for(int[] dir : directions){
                        int row = cell.row + dir[0];
                        int col = cell.col + dir[1];
                        if(row>0&&row<m && col>0&&col<n && !visited[row][col]){
                                visited[row][col] = true;
                                //使用方向max函数提高可读性
                                total += Math.max(0, cell.height-heights[row][col]);
                                queue.offer(new Cell(row,col,Math.max(heights[row][col],cell.height)));
                        }
                }
        }
        return total;
}