407. Trapping Rain Water II

这题也是很有意思的经典题目，是一道典型的BFS2的题目。
我们先看一下怎么理解它是BFS2的题目。因为我第一次做这题的时候真是没有看懂题意，花了好久。
能存多少水相当于每个点能存多少水加起来。
首先这种存水问题，边界上的点是肯定存不了水的因为假设周围是低地。
每个点存的水相当于从外面到这个点的最低cost - 这个点的高度。
最低cost就是最短路径呀！所以又是一个BFS2的问题。

这题和778 Swim in rising water 很像， 见 https://www.jianshu.com/p/19b50d3727a5
这题又和417. Pacific Atlantic Water Flow很像，不过 417那道不需要记cost，只需要记能不能到，所以那题只要BFS就好了。而407需要BFS2。
看代码

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int ans = 0;
        if (heightMap == null || heightMap.length < 2 ||
           heightMap[0].length < 2) return  0;
        int N = heightMap.length, M = heightMap[0].length;
        int h = Integer.MIN_VALUE;
        int[][] OFFSETS = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                if (o1[2] == o2[2]) return 0;
                return o1[2] < o2[2] ? -1 : 1;
            }
        });
        //put all boundry to queue
        putBoundryToQueue(heightMap, N, M, visited, queue);
        //bfs
        while(!queue.isEmpty()) {
            int[] pos = queue.poll();
            int r = pos[0], c = pos[1], localH = pos[2];
            h = localH;
            ans += localH - heightMap[r][c];
            for (int[] os : OFFSETS) {
                int nr = os[0] + r, nc = os[1] + c;
                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                if (visited[nr][nc]) continue;
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc, Math.max(heightMap[nr][nc], h)});
            }
        }
        return ans;
    }
    private void putBoundryToQueue(int[][] heightMap, int N, int M, boolean[][] visited,
                                  Queue<int[]> queue) {
        for (int r = 0; r < N; r++) {
            queue.offer(new int[] {r, 0, heightMap[r][0]});
            queue.offer(new int[] {r, M - 1, heightMap[r][M - 1]});
            visited[r][0] = true;
            visited[r][M - 1] = true;
        }
        for (int c = 1; c < M - 1; c++) {
            queue.offer(new int[] {0, c, heightMap[0][c]});
            queue.offer(new int[] {N - 1, c, heightMap[N - 1][c]});
            visited[0][c] = true;
            visited[N - 1][c] = true;
        }
    }
}