Score : $200$ points

问题描述

我们有一个棋盘，其横向有 $R$ 行，纵向有 $C$ 列。令 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的方格。

你被赋予了一些字符 $B_{i,j}$，它们代表了当前 $(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|$。

请打印出爆炸后棋盘的状态。

以上为通义千问 qwen-max 翻译，仅供参考。

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

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

update @ 2024/3/10 12:15:48