分数: 425 点
问题陈述
有一个网格 H 行和 W 列。我们称该单元格为 i从顶部算起的第行 (1\leq i\leq H) 和 j左起第 列 (1\leq j\leq W) 作为单元格 (i,j).
最初,细胞 (i,j) 为黑色,如果 S_{i,j} is # 和白色(如果是) ..
执行以下操作 10^{100} 次:
- 让 T 是一组白色单元格,并且恰好有一个相邻单元格黑色。为每个单元格着色 T 黑色。这里有两个单元格 (i_1,j_1) 和 (i_2,j_2) 相邻当且仅当 |i_1-i_2|+|j_1-j_2|=1.
求所有操作完成后黑色的单元格数量。
约束
- 2\leq H,W
- HW\leq 3\times 10^5
- H 和 W 是整数。
- S_{i,j} is
#or..
输入
输入由标准输入按以下格式给出:
H W
S_{1,1}S_{1,2}\ldots S_{1,W}
S_{2,1}S_{2,2}\ldots S_{2,W}
\vdots
S_{H,1}S_{H,2}\ldots S_{H,W}
输出
输出答案。
示例输入 1
9 9 ......... ......... ......... ......... ....#.... ......... ......... ......... .........
示例输出 1
57
通过操作,网格变化如下。 (上面的数字代表操作次数。显示前十次操作。)

最终, 57 单元格颜色为黑色。
示例输入 2
2 2 .. ..
示例输出 2
0
示例输入 3
10 10 .......... ....#..... #.......#. ......#... .......#.. .....#.... .......... .......... ..#...#... .......#..
示例输出 3
64