← 返回题目列表

AtCoder · abc460_d

G. 反复重新粉刷

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

分数: 425 点

问题陈述

有一个网格 H 行和 W 列。牢房位于 i从顶部开始的第行和 j从左边算起的第列称为单元格 (i, j).

每个单元格都是白色或黑色。网格描述为 H 字符串 S_1, S_2, \ldots, S_H,每个长度 W。如果 j- 第一个字符 S_i is .,细胞 (i, j) 为白色;如果 j- 第一个字符 S_i is #,细胞 (i, j) 是黑色的。

您执行以下操作 10^{100} 次。

  • 同时将以下规则应用于所有单元格。
    • 当且仅当存在至少一个与其相邻的黑色单元格时,操作前为白色的单元格才会变为黑色。在这里,细胞 (x, y) 和 (x', y') 相邻当且仅当其中之一在 8- 另一个的邻域,即 \max(|x-x'|, |y-y'|) = 1.
    • 操作前为黑色的单元格变为白色。

求运算后每个单元格的颜色。

约束

  • 1 \leq H \times W \leq 10^6
  • H 和 W 是正整数。
  • S_i 是一个长度为的字符串 W 组成 . 和 #.

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
\vdots
S_H

输出

输出 H 行。

输出一串长度 W 组成 . 和 # 每行。

的 j- 第一个字符 i- 第行应该是 . 如果细胞 (i, j) 后为白色 10^{100} 操作,以及 # 如果是黑色。


样本输入 1

3 4
#.#.
.#..
#...

示例输出 1

#.#.
.#..
#..#

最初,网格如下。

一次操作后,网格如下。

之后 10^{100} 作业时,网格如下。


示例输入 2

3 3
###
###
###

示例输出 2

...
...
...

示例输入 3

5 7
.#.....
.......
..#....
.......
....#..

示例输出 3

.#.##.#
....#..
#.#.###
#.....#
###.#.#