1

我正在尝试从 SPOJ 解决以下问题：

在包含 n m 个场的矩形网格上，放置 n m 个长方体，每个场上一个长方体。每个长方体的底面覆盖一个区域，其表面积等于一平方英寸。相邻场上的长方体彼此紧密相连，以至于它们之间没有间隙。一场大雨倾盆而下，在一些地方出现了水坑。

任务

编写一个程序：

  • 从标准输入中读取棋盘的大小和放置在场上的长方体的高度
  • 计算最大水量，雨后可能聚集在水坑中
  • 将结果写入标准输出。

输入

测试用例的数量 t 在输入的第一行，然后是 t 个测试用例，以空行分隔。在每个测试用例的第一行，写入两个正整数 1 <= n <= 100, 1 <= m <= 100。它们是网格的大小。在以下 n 行的每一行中，有 m 个来自区间 [1..10000] 的整数；第 j 行中的第 i 个数字表示长方体的高度，以英寸为单位，放在第 i 列和第 j 个棋盘上的场地上。

输出

你的程序应该为每个案例写一个等于最大水量的整数（以立方英寸为单位），它可能会聚集在结构上的水坑中。

Example

Sample input:
1
3 6
3 3 4 4 4 2
3 1 3 2 1 4
7 3 1 6 4 1

Sample output:
5

我正在使用 BFS 来添加从边界元素流入水坑的水量（如果找到任何路径）。但我无法处理水坑可能像两个连续的长方体的情况。任何人都可以帮我处理这个案子吗？

4

1 回答 1

2

这是我对这个问题的回答。为方便起见，我假设索引从 (1,1) 到 (M,N)

正如您可以想象的水流一样，水只能从较高的长方体流向较低的长方体（没有反向方向，即来自较低长方体的水会撞到较高长方体的壁并停在那里）。

所以我们构建图 G = (V,E) 使得 V 是 M x N 个顶点，即矩阵上的长方体。当 height(i) >= height(j) 并且（i 和 j 物理连接）时，边缘连接（仅 1 路）将长方体 i(th) 连接到长方体 j(th)

所以问题只是一个简单的 BFS。

顺便说一句，我发现另一个也解决了这个问题。请看一下

http://www.spojsolutions.com/212-water-among-cubes/

于 2012-09-13T10:51:52.070 回答