分数: 450 点
问题陈述
有一座大小不一的岛屿 H \times W,四面环海。
该岛分为 H 行和 W 列 1 \times 1 剖面,以及剖面处的高程 i从顶部开始的第行和 j从左边算起的第列(相对于当前海平面)是 A_{i,j}.
从现在开始,海平面上升 1 每年。
此处,垂直或水平毗邻大海的部分或沉入大海的部分具有标高 不大于 海平面将沉入大海。
这里,当一个区段新沉入海中时,任何垂直或水平相邻且标高不大于海平面的区段也将同时沉入海中,并且对于新沉入的区段重复此过程。
对于每个 i=1,2,\ldots, Y,找出岛屿仍高于海平面的面积 i 从现在起。
约束
- 1 \leq H, W \leq 1000
- 1 \leq Y \leq 10^5
- 1 \leq A_{i,j} \leq 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W Y
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
输出
打印 Y 行。 的 i第行 (1 \leq i \leq Y) 应包含岛屿仍高于海平面的区域 i 从现在起。
示例输入 1
3 3 5 10 2 10 3 1 4 10 5 10
示例输出 1
9 7 6 5 4
让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。然后,会发生以下情况:
- 之后 1 年,海平面比现在高 1,但没有标高为 1 毗邻大海,因此没有部分下沉。因此,第一行应该包含 9.
- 之后 2 年,海平面比现在高 2,和 (1,2) 沉入大海。这使得 (2,2) 毗邻凹陷部分,其标高不大于 2,所以它也会下沉。此时没有其他部分下沉。因此,两个部分下沉,第二行应包含 9-2=7.
- 之后 3 年,海平面比现在高 3,和 (2,1) 沉入大海。没有其他部分下沉。因此,第三行应该包含 6.
- 之后 4 年,海平面比现在高 4,和 (2,3) 沉入大海。没有其他部分下沉。因此,第四行应该包含 5.
- 之后 5 年,海平面比现在高 5,和 (3,2) 沉入大海。没有其他部分下沉。因此,第五行应该包含 4.
因此,打印 9, 7, 6, 5, 4 按照这个顺序,每一个都换行。
示例输入 2
3 5 3 2 2 3 3 3 2 1 2 1 3 2 2 3 3 3
示例输出 2
15 7 0