当前位置:首页 > 图论 > 最短路径 > 正文
51NOD-冬奥会之积水问题
259+

题目大意:给定一个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)。

About

坚决不Copy代码!

本文标签:,,,,,,,,

51NOD-冬奥会之积水问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!