P5930 [POI1999] 降水 题解

· · 题解

本人认为此题应该在普及- 难度，请各位萌新放心食用。

1.题面分析

从此题面中，不难看出：只有四周的土地均高于这块地的时候，那么才能积水。

那么第一个问题就诞生了：怎么知道哪个坑里存着水呢？

以样例为例：

3 6
3 3 4 4 4 2
3 1 3 2 1 4
7 3 1 6 4 1

这里的数字有哪个是在被比他大的数字包围呢？ 这里很明显，我圈出来的数字是被包裹着的。所以明显可以知道，存水的标准时被四周的大于它的数包围，或与它连成块（一样或更少）的水域被大数包围，才能存水。

第一个问题解决了。

然后出来了第二个问题：如何计算积攒的水的多少？

依然以样例为例：

3 6
3 3 4 4 4 2
3 1 3 2 1 4
7 3 1 6 4 1

大家看出来了吗？对，我箭头指向的都是被包裹的数字附近最小的数字。

让我们来算算。

第2行第2列，附近最大数为3。3 - 1=2。2-1=1。所以水的英寸数+1。也就是说，积攒的数量也就是附近最大数-2。 以此类推。

最终我们得出 算一算，正好是样例所给的5。

二.代码部分

再次读题，方法显而易见。遍历数字，然后遍历这个数周围的数是否是超过它。这像不像某个算法？对，它就是BFS，但实际上其实我们并不需要用到BFS。只用两层for就行了。

搜索的坐标如下图：

通过这张图我们可以得出如下代码：

if(a[i][j-1]>maxi){
    maxi=a[i][j-1];
}
if(a[i-1][j]>maxi){
    maxi=a[i-1][j];
}
if(a[i][j+1]>maxi){
    maxi=a[i][j+1];
}
if(a[i+1][j]>maxi){
    maxi=a[i+1][j];
}

注：maxi为附近最大数