A7704. Repeatedly Repainting
编程题
入门
知识点
题目描述
有一个 $H$ 行 $W$ 列的网格。从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子称为格子 $(i, j)$。
每个格子为白色或黑色。该网格由 $H$ 个长度均为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 描述。若 $S_i$ 的第 $j$ 个字符为
你将执行以下操作 $10^{100}$ 次：
* 同时对所有格子应用如下规则：
* 若一个格子在操作前为白色，则当且仅当其至少有一个相邻的黑色格子时，它在操作后变为黑色。其中，格子 $(x, y)$ 与 $(x', y')$ 相邻，当且仅当其中一个格子位于另一个格子的八邻域内，即 $\max(|x-x'|, |y-y'|) = 1$。
* 若一个格子在操作前为黑色，则它在操作后变为白色。
求所有格子在执行完所有操作后的颜色。
每个格子为白色或黑色。该网格由 $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$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
输出格式
输出 $H$ 行。
每行输出一个长度为 $W$ 的字符串，该字符串仅由字符
第 $i$ 行的第 $j$ 个字符应为
每行输出一个长度为 $W$ 的字符串，该字符串仅由字符
. 和 # 组成。第 $i$ 行的第 $j$ 个字符应为
.（若经过 $10^{100}$ 次操作后，格子 $(i, j)$ 为白色），或 #（若其为黑色）。输入输出样例
输入 #1
3 4 #.#. .#.. #...
输出 #1
#.#. .#.. #..#
输入 #2
3 3 ### ### ###
输出 #2
... ... ...
输入 #3
5 7 .#..... ....... ..#.... ....... ....#..
输出 #3
.#.##.# ....#.. #.#.### #.....# ###.#.#
说明/提示
**样例 1 解释：**
初始时，网格如下所示。
经过一次操作后，网格如下所示。
经过 $10^{100}$ 次操作后，网格如下所示。
### 约束条件
* $1 \leq H \times W \leq 10^6$
* $H$ 和 $W$ 均为正整数。
* $S_i$ 是一个长度为 $W$ 的字符串，仅由字符
初始时，网格如下所示。
经过一次操作后，网格如下所示。
经过 $10^{100}$ 次操作后，网格如下所示。
### 约束条件
* $1 \leq H \times W \leq 10^6$
* $H$ 和 $W$ 均为正整数。
* $S_i$ 是一个长度为 $W$ 的字符串，仅由字符
. 和 # 组成。