B - Minesweeper

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200

問題文

H × W のマス目が与えられます。
入力において、全てのマスは文字で表されており、.は空きマス、 # は爆弾マスに対応します。
マス目は H 個の文字列 S_1,...,S_H で表されます。
文字列 S_ij 文字目は、マス目の上から i 番目、左から j 番目のマスに対応します。(1≦i≦H,1≦j≦W)

イルカは各空きマスの上下左右および斜めの 8 方向で隣接しているマスに爆弾マスが何個あるか気になっています。
そこで、各空きマスに対応する . を、その空きマスの周囲8方向に隣接するマスにおける爆弾マスの個数を表す数字で置き換えることにしました。

以上の規則で置き換えられた後のマス目を出力してください。

制約

  • 1≦H,W≦50
  • S_i#. からなる長さ W の文字列

入力

入力は以下の形式で標準入力から与えられる。

H W 
S_1
:
S_H

出力

置き換えられた後のマス目を H 行の文字列で出力せよ。
i 行目 に出力する文字列 T_i の長さは W であり、 T_ij 文字目は、置き換えられた後のマス目の上から i 番目、左から j 番目のマスに対応させよ。(1≦i≦H,1≦j≦W)


入力例 1

3 5
.....
.#.#.
.....

出力例 1

11211
1#2#1
11211

例として、上から 1 番目、左から 1 番目の空きマスに注目します。
この空きマスの周囲の 8 マスに含まれる爆弾マスは、上から 2 番目、左から 2 番目のマスのみです。 したがって、上から 1 番目、左から 1 番目の空きマスは 1 に置き換えられています。


入力例 2

3 5
#####
#####
#####

出力例 2

#####
#####
#####

空きマスが存在しない場合があります。


入力例 3

6 6
#####.
#.#.##
####.#
.#..#.
#.##..
#.#...

出力例 3

#####3
#8#7##
####5#
4#65#2
#5##21
#4#310

Score : 200 points

Problem Statement

You are given an H × W grid.
The squares in the grid are described by H strings, S_1,...,S_H.
The j-th character in the string S_i corresponds to the square at the i-th row from the top and j-th column from the left (1 \leq i \leq H,1 \leq j \leq W).
. stands for an empty square, and # stands for a square containing a bomb.

Dolphin is interested in how many bomb squares are horizontally, vertically or diagonally adjacent to each empty square.
(Below, we will simply say "adjacent" for this meaning. For each square, there are at most eight adjacent squares.)
He decides to replace each . in our H strings with a digit that represents the number of bomb squares adjacent to the corresponding empty square.

Print the strings after the process.

Constraints

  • 1 \leq H,W \leq 50
  • S_i is a string of length W consisting of # and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the H strings after the process.
The i-th line should contain a string T_i of length W, where the j-th character in T_i corresponds to the square at the i-th row from the top and j-th row from the left in the grid (1 \leq i \leq H, 1 \leq j \leq W).


Sample Input 1

3 5
.....
.#.#.
.....

Sample Output 1

11211
1#2#1
11211

For example, let us observe the empty square at the first row from the top and first column from the left.
There is one bomb square adjacent to this empty square: the square at the second row and second column.
Thus, the . corresponding to this empty square is replaced with 1.


Sample Input 2

3 5
#####
#####
#####

Sample Output 2

#####
#####
#####

It is possible that there is no empty square.


Sample Input 3

6 6
#####.
#.#.##
####.#
.#..#.
#.##..
#.#...

Sample Output 3

#####3
#8#7##
####5#
4#65#2
#5##21
#4#310