← 返回题目
题库练习 Repeatedly Repainting
← 上一题 下一题 →

A7704 | Repeatedly Repainting

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

有一个 $H$ 行 $W$ 列的网格。从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子称为格子 $(i, j)$。

每个格子为白色或黑色。该网格由 $H$ 个长度均为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 描述。若 $S_i$ 的第 $j$ 个字符为 .，则格子 $(i, j)$ 为白色；若为 #，则格子 $(i, j)$ 为黑色。

你将执行以下操作 $10^{100}$ 次：

* 同时对所有格子应用如下规则：
* 若一个格子在操作前为白色，则当且仅当其至少有一个相邻的黑色格子时，它在操作后变为黑色。其中，格子 $(x, y)$ 与 $(x', y')$ 相邻，当且仅当其中一个格子位于另一个格子的八邻域内，即 $\max(|x-x'|, |y-y'|) = 1$。
* 若一个格子在操作前为黑色，则它在操作后变为白色。

求所有格子在执行完所有操作后的颜色。

输入格式

输入从标准输入中按以下格式给出：

> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$

输出格式

输出 $H$ 行。

每行输出一个长度为 $W$ 的字符串，该字符串仅由字符 . 和 # 组成。

第 $i$ 行的第 $j$ 个字符应为 .（若经过 $10^{100}$ 次操作后，格子 $(i, j)$ 为白色），或 #（若其为黑色）。

输入输出样例

输入 #1
3 4
#.#.
.#..
#...
输出 #1
#.#.
.#..
#..#
输入 #2
3 3
###
###
###
输出 #2
...
...
...
输入 #3
5 7
.#.....
.......
..#....
.......
....#..
输出 #3
.#.##.#
....#..
#.#.###
#.....#
###.#.#
C++ 编辑器
输入
输出