/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
縦 R 行横 C 列の盤面があります。上から i 行目、左から j 列目のマスを (i,j) と表します。
(i,j) の現在の状態が文字 B_{i,j} として与えられます。
. は空きマス、# は壁があるマスを表し、
1, 2,\dots, 9 はそれぞれ威力 1,2,\dots,9 の爆弾があるマスを表します。
次の瞬間に、全ての爆弾が同時に爆発します。 爆弾が爆発すると、爆弾があるマスからのマンハッタン距離がその爆弾の威力以下であるような全てのマス（その爆弾があるマス自体を含む）が空きマスに変わります。 ここで、(r_1,c_1) から (r_2,c_2) までのマンハッタン距離は |r_1-r_2|+|c_1-c_2| です。
爆発後の盤面を出力してください。
制約
- 1\leq R,C \leq 20
- R,C は整数
- B_{i,j} は
.,#,1,2,\dots,9のいずれかである
入力
入力は以下の形式で標準入力から与えられる。
R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}
出力
爆発後の盤面を R 行で出力せよ。盤面の表し方は入力と同じ形式を用いること (R と C を出力する必要はない)。
入力例 1
4 4 .1.# ###. .#2. #.##
出力例 1
...# #... .... #...
- (1,2) にある爆弾の爆発によって、上図の青いマスと紫のマスが空きマスに変わります。
- (3,3) にある爆弾の爆発によって、上図の赤いマスと紫のマスが空きマスに変わります。
この例のように、爆弾が効果を及ぼす範囲に被りがあることもあります。
入力例 2
2 5 ..#.# ###.#
出力例 2
..#.# ###.#
爆弾が 1 つもないこともあります。
入力例 3
2 3 11# ###
出力例 3
... ..#
入力例 4
4 6 #.#3#. ###.#. ##.### #1..#.
出力例 4
...... #..... #....# ....#.
Score : 200 points
Problem Statement
We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
You are given characters B_{i,j} representing the current states of (i,j).
. represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.
At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.
Print the board after the explosions.
Constraints
- 1\leq R,C \leq 20
- R and C are integers.
- Each B_{i,j} is one of
.,#,1,2, \dots,9.
Input
The input is given from Standard Input in the following format:
R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}
Output
Print R lines representing the board after the explosions. Use the format used in the input (do not print R or C).
Sample Input 1
4 4 .1.# ###. .#2. #.##
Sample Output 1
...# #... .... #...
- The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
- The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.
As seen in this sample, the explosion ranges of bombs may overlap.
Sample Input 2
2 5 ..#.# ###.#
Sample Output 2
..#.# ###.#
There may be no bombs.
Sample Input 3
2 3 11# ###
Sample Output 3
... ..#
Sample Input 4
4 6 #.#3#. ###.#. ##.### #1..#.
Sample Output 4
...... #..... #....# ....#.