题目描述

blablabla

样例

import java.util.*;
class Main{
    // 我们有很多条路径  我们知道水在某条路径(或者某个方向) 中可以 存多少取决于这个路径中的最大高度 （一维比如左边最大高度）
    // 但很多路径 取决于所有路径最大高度中最小的那个   （一维取决于 左右最大高度中小的那个） 
    //  f(i, j) 为这个点最大可放雨水的高度  就是遍历四周 但是我们只需要知道最小就可以了 所以我们用minheap 这个点cur被poll出来
    // 发现和四周对比 如果没有被 visited 那就加入queue继续遍历(并且高度为Math.max(cur[2], h[nr][nc])) 因为高度可能更新
    // 在加入queue前发现这个点高度小于 cur[2] 我们知道cur[2] 已经是某条路径中最大值中最小的(我们每次加入的都是Math.max(f(i, j), cur[2])
    // 那么可以存水量是cur[2] 减去 原本高度h[i][j] 就是这个点可以存的水 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int k = 1; k <= t; k++) {
            int r = sc.nextInt(), c = sc.nextInt();
            int[][] h = new int[r][c];
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    h[i][j] = sc.nextInt();
                }
            }
            int x = trapRain(h);
            System.out.println("Case #" + k + ": " + x); // 这个output 调了一会儿 很恶心
        }
    }

    public static int trapRain(int[][] h) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        int n = h.length, m = h[0].length;
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            visited[i][0] = true;
            visited[i][m - 1] = true;
            queue.offer(new int[]{i, 0, h[i][0]});
            queue.offer(new int[]{i, m - 1, h[i][m - 1]});
        }

        for (int j = 1; j < m - 1; j++) {
            visited[0][j] = true;
            visited[n - 1][j] = true;
            queue.offer(new int[]{0, j, h[0][j]});
            queue.offer(new int[]{n - 1, j, h[n - 1][j]});
        }

        int res = 0;
        int[] drow = {1, 0, -1, 0}, dcol = {0, 1, 0, -1};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nr = cur[0] + drow[i], nc = cur[1] + dcol[i];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;
                if (h[nr][nc] < cur[2]) res += cur[2] - h[nr][nc];
                queue.offer(new int[]{nr, nc, Math.max(cur[2], h[nr][nc])}); //这里更新f(nr, nc)高度（没在h中修改）  
                visited[nr][nc] = true;
            }
        }
        return res;
    }
}
blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla