← 返回题目列表

AtCoder · abc425_d

G. 乌拉姆-沃伯顿自动机

中文机器翻译题面 查看原题

分数: 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