← 返回题目列表

AtCoder · abc363_e

H. 下沉的土地

中文机器翻译题面 查看原题

分数: 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