#Summer2400206. 下沉的陆地

下沉的陆地

下沉的陆地

题目描述

有一个面积为 H×WH \times W 的小岛,四面环海。 该岛被分成 HH 行和 WW 列的 1×11×1 个部分,从顶部起 ii 行和从左侧起 jj 列的部分(相对于当前海平面)的海拔高度为 Ai,jA_{i,j}

从现在开始,海平面每年上升 11 。 在这里,垂直或水平临海的地段或沉入海中的地段,其标高不大于海平面,就会沉入海中。 在这里,当一个断面新z沉入海中时,垂直或水平相邻的标高不大于海平面的断面也会同时沉入海中,新沉入海中的断面重复这一过程。

对于每个 i=1,2,,Yi=1,2, \dots,Y ,求 ii 年后该岛仍高于海平面的面积。

输入格式

输入内容由标准输入法提供,格式如下:

HH WW YY A1,1A_{1,1} A1,2A_{1,2} \ldots A1,WA_{1,W} A2,1A_{2,1} A2,2A_{2,2} \ldots A2,WA_{2,W} \vdots AH,1A_{H,1} AH,2A_{H,2} \ldots AH,WA_{H,W}

输出格式

打印 YY 行。 第 ii(1iY)(1 \leq i \leq Y) 应该包含从现在起 ii 年后海平面以上的岛屿面积。

样例 #1

样例输入 #1

3 3 5
10 2 10
3 1 4
10 5 10

样例输出 #1

9
7
6
5
4

样例 #2

样例输入 #2

3 5 3
2 2 3 3 3
2 1 2 1 3
2 2 3 3 3

样例输出 #2

15
7
0

提示

数据范围

  • 1 H,W 1000 1\leq\ H,W\leq\ 1000
  • 1 Y 105 1\leq\ Y\leq\ 10^5
  • 1 Ai,j 105 1\leq\ A_{i,j}\leq\ 10^5
  • 所有输入值均为整数。

样例 11 解释

(i,j)(i,j) 表示从上往下第 ii 行和从左往上第 jj 列的部分。然后,会发生以下情况:

  • 11 年之后,海平面比现在高出 11,但是没有海拔高度为 11 的地段与海相邻,所以没有地段下沉。因此,第一行应包含 99
  • 22 年后,海平面比现在高出 22(1,2)(1,2) 沉入海中。这使得 (2,2)(2,2) 与下沉地段相邻,其海拔高度不高于 22 ,所以也下沉了。此时没有其他地段下沉。因此,有两个部分下沉,第二行应包含 92=79−2=7
  • 33 年后,海平面比现在高出 33(2,1)(2,1) 沉入海中。其他部分没有下沉。因此,第三行应包含 66
  • 44 年后,海平面比现在高出 44(2,3)(2,3) 沉入大海。其他部分没有下沉。因此,第四行应包含 55
  • 55 年后,海平面比现在高出 55(3,2)(3,2) 沉入大海。其他部分没有下沉。因此,第五行应包含 44

因此,依次打印 9977665544 ,每行打印一行。