51NOD-冬奥会之积水问题
699+
作者：crxis 发布：2021-12-07 分类：最短路径
题目大意：给定一个n*n的地形图，低洼出会积水，请问积水量是多少？
冬奥会赛场旁有一片正方形的洼地（长宽都为n），地形凹凸不平，洼地的四周是一圈排水池。有一天，下了很大的雨，洼地形成了积水，告诉你洼地的地形（n*n块的高度），由你来计算，洼地的积水量。
例如：n = 4
3 4 5 6
4 1 2 7
5 1 2 8
6 7 8 9
因为四周都是排水池（边界上的水会通过排水池流走），最终只有橘色部分：
1 2
1 2
能够形成积水，积水高度由他们4周（绿色部分）的最低高度决定，这个高度是4（左上角0，0位置的3虽然小于4，但2个高度为4的方块已经形成了封闭的一圈），所以总的积水量是10。
输入
第一行：一个数n，表示洼地的大小（3 <= n <= 1000) 后面n行：每行n个数，表示地形的高度h[i,j]（0 <= h[i,j] <= 1000000）。
输出
输出总的积水量。
输入样例
4 3 4 5 6 4 1 2 7 5 1 2 8 6 7 8 9
输出样例
10
解题思路
木桶效应：水的高度，取决于最短的那根木板的高度。
每个位置的积水量，取决于周围的高度的最小值。什么是周围的高度？即该位置走到外围的路径上的最大值。也就是说，我们需要求的是每个位置到外围的所有路径最大值中的最小值。
程序实现
从里面每个位置跑最短路会超时；我们可以以外围为起点，跑一次最短路，即预处理出每个位置水的高度，累加高度差即答案。
贪心做法：依次使用“最短的木板”，寻找他能拦截的水量。使用最短的目标，进行填充，低洼出会积水，高处则形成新的木板。不断把木板放入队列，出队寻找积水即可。
使用邻接表存储同一个高度的木板，实现单调队列，时间复杂度O(n*m)。
