P12019 [NOISG 2025 Finals] 洪水

Pavementland 是一座城市，可以用一个 $h \times w$ 的矩形网格表示。网格的行从北到南编号为 $1$ 到 $h$，列从西到东编号为 $1$ 到 $w$。我们将位于网格第 $r$ 行、第 $c$ 列的单元格称为单元格 $(r, c)$。 在网格中，每个单元格要么是空的，要么包含一座建筑。至少有一个单元格是空的。 由于季风暴潮，Pavementland 发生了突发洪水。最初，一场降雨导致某个空单元格被水淹没。然后，水按照以下规则流动： - 如果一个空单元格与至少一个被淹没的单元格相邻，它也会被淹没。 - 如果一个包含建筑的单元格与至少两个被淹没的单元格相邻，该建筑会倒塌，该单元格变为被淹没状态。 请注意，如果两个单元格共享一条边，则它们是相邻的。一个单元格最多可以与四个其他单元格相邻。进一步说明，水不会流出网格范围。令 $f((r, c))$ 表示如果单元格 $(r, c)$ 最初被淹没，则最终被淹没的单元格总数。 市政官员希望预测所有可能情况下的洪水蔓延范围。请帮助他们计算所有空单元格 $(r, c)$ 的 $f((r, c))$ 之和。

无

无

### 子任务 对于所有测试用例，输入将满足以下约束条件： - $1 \leq h, w \leq 5000$ - 网格中至少有一个空单元格。 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分数 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $0$ | 样例 | | $1$ | $5$ | $h = 1$ | | $2$ | $7$ | $h, w \leq 80$ | | $3$ | $16$ | $h, w \leq 500$ | | $4$ | $32$ | $h, w \leq 2000$ | | $5$ | $40$ | 无 | ### 样例 1 解释 此样例适用于子任务 $2$ 至 $5$。 如果单元格 $(1, 1), (1, 2), (1, 3), (2, 1)$ 或 $(3, 1)$ 最初被淹没，则整个网格最终都会被淹没。如果单元格 $(3, 3)$ 最初被淹没，则最终只有 $1$ 个单元格被淹没。因此，输出为 $9 + 9 + 9 + 9 + 9 + 1 = 46$。 ### 样例 2 解释 此样例适用于子任务 $2$ 至 $5$。 ### 样例 3 解释 此样例适用于所有子任务。