Responsive image

问题 2384 --雨

2384: 雨

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

海里有一个小岛。
岛可以描述为一个具有 R 行 C 列的矩阵,其中包含的数字 H[i][j] 表示每个单元格的高度。
以下是一个 3×3 岛屿的示例:
3 5 5
5 4 5
5 5 5
有时,大雨会在这个岛上的每个单元格上均匀地降落。
你可以假设降水量可以是无限大。
在这样的大雨之后,岛上的一些区域(由沿着边缘连接的一个或多个单元格形成)可能会存在积水。
一片区域可以存在积水的前提是与该区域内单元格沿着边缘连接的区域外的单元格的高度均高于区域内单元格。(周围的海洋被视为高度为 0 的无限单元格。)
否则,水将始终流入其他区域并最终出海。
你可以假设海的高度永远不会改变。
在大雨过后,我们将使用 W[i][j] 来表示岛屿上每个单元格的高度。
以下是对大雨过后的示例岛屿的高度的分析。
最中央的初始高度为 4 的单元格被初始高度为 5 的单元格包围着,因此在该单元格将产生积水,在积水高度到达 5 以后,没有更多区域被高度更高的单元格包围,因此将不再继续积水。
请注意,水不会直接在两个共享顶点的单元格之间流动;水必须沿着共同的边缘流动。(所以中央单元格的积水不会从左上角处流走)
以下是雨后示例岛屿的高度:
3 5 5
5 5 5
5 5 5
给定岛的高度矩阵,你能计算出大雨后的每个单元格的增加高度(W[i][j]−H[i][j])的总和吗?

输入描述

第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 R 和 C。
接下来 R 行每行包含 C 个整数 H[i][j],表示矩阵内单元格的高度。

输出描述

每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y,其中 x 是组别编号(从 1 开始),y 是增加高度的总和。

样例输入

3
3 3
3 5 5
5 4 5
5 5 5
4 4
5 5 5 1
5 1 1 5
5 1 5 5
5 2 5 8
4 3
2 2 2
2 1 2
2 1 2
2 1 2

样例输出

Case #1: 1
Case #2: 3
Case #3: 0

提示

1≤T≤100,

1≤H[i][j]≤1000,

1≤R,C≤50

来源

[提交][状态]
ACM算法攻关部