The Labyrinth

题面翻译

给你一张图，‘’表示墙，‘.’表示空地，问每个''周围的联通快中‘.’的数量和 mod 10，属于同一个联通快的只计算一次。

题目描述

You are given a rectangular field of $n×m$ cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell $(x,y)$ imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains $(x,y)$ . You should do it for each impassable cell independently.

The answer should be printed as a matrix with $n$ rows and $m$ columns. The $j$ -th symbol of the $i$ -th row should be "." if the cell is empty at the start. Otherwise the $j$ -th symbol of the $i$ -th row should contain the only digit —- the answer modulo $10$ . The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of $n$ strings having length $m$ and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

输入格式

The first line contains two integers $n,m$ ( $1<=n,m<=1000$ ) — the number of rows and columns in the field.

Each of the next $n$ lines contains $m$ symbols: "." for empty cells, "*" for impassable cells.

输出格式

Print the answer as a matrix as described above. See the examples to precise the format of the output.

样例 #1

样例输入 #1

3 3
*.*
.*.
*.*

样例输出 #1

3.3
.5.
3.3

样例 #2

样例输入 #2

4 5
**..*
..***
.*.*.
*.*.*

样例输出 #2

46..3
..732
.6.4.
5.4.3

提示

In first example, if we imagine that the central cell is empty then it will be included to component of size $5$ (cross). If any of the corner cell will be empty then it will be included to component of size $3$ (corner).