/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
H 行 W 列のマス目があります。このマス目の上から i 行目、左から j 列目のマスをマス (i, j) と呼びます。
すべてのマスは白または黒で塗られています。マス目の情報は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H によって与えられ、S_i の j 文字目が . のときマス (i, j) は白で、S_i の j 文字目が # のときマス (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 の文字列を 1 つずつ出力せよ。
i 行目の文字列の j 文字目は 10^{100} 回の操作を行った後にマス (i, j) が白で塗られているとき . に、黒で塗られているとき # になるようにせよ。
入力例 1
3 4 #.#. .#.. #...
出力例 1
#.#. .#.. #..#
はじめ、マス目は以下のようになっています。
1 回操作を行うと、マス目は以下のようになります。
10^{100} 回操作を行うと、マス目は以下のようになります。
入力例 2
3 3 ### ### ###
出力例 2
... ... ...
入力例 3
5 7 .#..... ....... ..#.... ....... ....#..
出力例 3
.#.##.# ....#.. #.#.### #.....# ###.#.#
Score : 425 points
Problem Statement
There is a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j).
Every cell is colored white or black. The grid is described by H strings S_1, S_2, \ldots, S_H, each of length W. If the j-th character of S_i is ., cell (i, j) is white; if the j-th character of S_i is #, cell (i, j) is black.
You perform the following operation 10^{100} times.
- Simultaneously apply the following rules to all cells.
- A cell that is white before the operation becomes black if and only if there exists at least one black cell adjacent to it. Here, cells (x, y) and (x', y') are adjacent if and only if one of them is within the 8-neighborhood of the other, that is, \max(|x-x'|, |y-y'|) = 1.
- A cell that is black before the operation becomes white.
Find the color of each cell after the operations.
Constraints
- 1 \leq H \times W \leq 10^6
- H and W are positive integers.
- S_i is a string of length W consisting of
.and#.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Output H lines.
Output one string of length W consisting of . and # per line.
The j-th character of the i-th line should be . if cell (i, j) is white after 10^{100} operations, and # if it is black.
Sample Input 1
3 4 #.#. .#.. #...
Sample Output 1
#.#. .#.. #..#
Initially, the grid is as follows.
After one operation, the grid is as follows.
After 10^{100} operations, the grid is as follows.
Sample Input 2
3 3 ### ### ###
Sample Output 2
... ... ...
Sample Input 3
5 7 .#..... ....... ..#.... ....... ....#..
Sample Output 3
.#.##.# ....#.. #.#.### #.....# ###.#.#