题目描述

译自 NOISG 2025 Final T5. Flooding

铺路国是一个矩形城市，可建模为一个 $h \times w$ 的网格。网格的行从北到南编号为 $1$ 到 $h$，列从西到东编号为 $1$ 到 $w$。位于行 $r$ 和列 $c$ 的格子称为格子 $(r, c)$。

在网格中，每个格子要么为空，要么包含建筑。至少有一个格子为空。

由于季风雨激增，铺路国正在发生突发性洪水。初始时，一个空格子因降雨而被洪水淹没。随后，洪水按以下规则流动：

• 若一个空格子与至少一个被淹没的格子相邻，该格子将被淹没。
• 若一个包含建筑的格子与至少两个被淹没的格子相邻，该建筑将倒塌，格子将被淹没。

注意，两个格子若共享一条边，则视为相邻。一个格子最多与四个其他格子相邻。另需注意，洪水不会流出网格。设 $f((r, c))$ 表示若格子 $(r, c)$ 初始被淹没，洪水流动过程结束后被淹没的格子数量。

城市官员希望预测所有可能情况下的洪水范围。请帮助他们计算所有空格子 $(r, c)$ 的 $f((r, c))$ 之和。

输入格式

程序需从标准输入读取数据。

输入的第一行包含两个空格分隔的整数 $h$ 和 $w$。

接下来的 $h$ 行，每行包含一个长度为 $w$ 的二进制字符串。若第 $r$ 行的第 $c$ 个字符为 0，则格子 $(r, c)$ 为空；若为 1，则格子 $(r, c)$ 包含建筑。

输出格式

程序需向标准输出输出结果。

输出一个整数，表示所有空格子 $(r, c)$ 的 $f((r, c))$ 之和。

3 3
000
011
010

46

若格子 $(1,1), (1,2), (1,3), (2,1), (3,1)$ 初始被淹没，洪水流动过程结束后整个网格将被淹没。若格子 $(3,3)$ 初始被淹没，过程结束后仅 $1$ 个格子被淹没。因此，输出为 $9+9+9+9+9+1=46$。

这个样例满足子任务 $2,3,4,5$ 的限制。

5 5
00101
01011
11010
01101
11000

182

这个样例满足子任务 $2,3,4,5$ 的限制。

1 10
1101011100

6

这个样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq h, w \leq 5000$
• 网格中至少有一个空格子。

详细子任务附加限制及分值如下表所示：