Sinking Land

题目描述

有一个大小为 $H \times W$ 的岛屿，四周被海洋包围。
岛屿被划分为 $H$ 行 $W$ 列的 $1 \times 1$ 的格子，第 $i$ 行（自上而下）第 $j$ 列（自左而右）的格子相对于当前海平面的高度为 $A_{i,j}$。 从现在起，海平面每年上升 $1$。
这里，如果一个格子与海洋或已沉入海中的格子在垂直或水平方向上相邻，且其高度不大于海平面，则该格子会沉入海中。
当一个格子新沉入海中时，与该格子垂直或水平方向相邻且高度不大于海平面的格子也会同时沉入海中，这个过程会对新沉没的格子重复进行。 对于每个 $i=1,2,\ldots, Y$，求从现在起 $i$ 年后仍然高于海平面的岛屿面积。

输入格式

输入按下述格式由标准输入提供： $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$ 年后仍然高于海平面的岛屿面积。

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

9
7
6
5
4

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

15
7
0

提示

$1 \leq H, W \leq 1000$ $1 \leq Y \leq 10^5$ $1 \leq A_{i,j} \leq 10^5$ 所有输入值均为整数。记 $(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$，每个数字占一行。

标签: AtCoder|abc363E

来源

AtCoder|abc363E