题目描述

Pavementland 是一座城市，可以用一个 $h \times w$ 的矩形网格表示。网格的行从北到南编号为 $1$ 到 $h$，列从西到东编号为 $1$ 到 $w$。我们将位于网格第 $r$ 行、第 $c$ 列的单元格称为单元格 $(r, c)$。

在网格中，每个单元格要么是空的，要么包含一座建筑。至少有一个单元格是空的。

由于季风暴潮，Pavementland 发生了突发洪水。最初，一场降雨导致某个空单元格被水淹没。然后，水按照以下规则流动：

• 如果一个空单元格与至少一个被淹没的单元格相邻，它也会被淹没。
• 如果一个包含建筑的单元格与至少两个被淹没的单元格相邻，该建筑会倒塌，该单元格变为被淹没状态。

请注意，如果两个单元格共享一条边，则它们是相邻的。一个单元格最多可以与四个其他单元格相邻。进一步说明，水不会流出网格范围。令 $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

5 5
00101
01011
11010
01101
11000

182

1 10
1101011100

6

提示

子任务

对于所有测试用例，输入将满足以下约束条件：

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

你的程序将在满足以下特殊性质的输入数据上进行测试：

样例 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 解释

此样例适用于所有子任务。