AT_abc363_e [ABC363E] Sinking Land

题目描述

有一个大小为 $H \times W$ 的岛屿，岛屿被海洋包围。
岛屿被划分为纵向 $H$ 个、横向 $W$ 个 $1\times 1$ 的小区块，从上到下第 $i$ 行、从左到右第 $j$ 列的区块的（以当前海平面为基准的）海拔为 $A_{i,j}$。

从现在起，每过 $1$ 年，海平面高度就上升 $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$ 年后未被海水淹没的岛屿面积。

输入输出样例 #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\leq H,W\leq 1000$
• $1\leq Y\leq 10^5$
• $1\leq A_{i,j}\leq 10^5$
• 输入均为整数

样例解释 1

用 $(i,j)$ 表示岛屿从上到下第 $i$ 行、从左到右第 $j$ 列的区块。此时，过程如下：

• 1 年后，海平面比现在上升 $1$，但没有与海洋相邻且海拔为 $1$ 的区块，因此没有区块被淹没。所以第 1 行输出 $9$。
• 2 年后，海平面比现在上升 $2$，$(1,2)$ 被海水淹没。由于 $(2,2)$ 与已被淹没的区块相邻且海拔不高于 $2$，也会被淹没。除此之外没有其他区块被淹没。因此有 $2$ 个区块被淹没，第 2 行输出 $9-2=7$。
• 3 年后，海平面比现在上升 $3$，$(2,1)$ 新被海水淹没。没有其他区块被淹没。因此第 3 行输出 $6$。
• 4 年后，海平面比现在上升 $4$，$(2,3)$ 新被海水淹没。没有其他区块被淹没。因此第 4 行输出 $5$。
• 5 年后，海平面比现在上升 $5$，$(3,2)$ 新被海水淹没。没有其他区块被淹没。因此第 5 行输出 $4$。

因此，依次输出 $9,7,6,5,4$。

由 ChatGPT 4.1 翻译