问题 4663 --迷宫

4663: 迷宫★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 59  解决: 25
[提交][状态][命题人:]

题目描述

给你一个n × m单元格的矩形区域。每个单元格要么为空,要么无法通行(包含障碍物)。空单元格用“.”标记,不可通过的单元格用“*”标记。如果两个空单元格共用一边,我们就称它们相邻。

对于每个不可通过的单元格(x, y),假设它是一个空单元格(所有其他单元格保持不变),并找到包含(x, y)的连通块的大小(单元格的数量)。你应该对每个无法通过的单元格独立地进行处理。

答案应打印为n行m列的矩阵。如果单元格空,则第i行的第j个符号应为“.”。否则,第i行的第j个符号应包含唯一的数字——对10取余的答案。矩阵输出时不应有任何空格。 

为了使输出更快,建议将输出构建为长度为m的n个字符串数组,并以行序列的形式输出。这将比一个一个地输出要快得多。

输入

第一行包含两个整数n, m(1 ≤ n,m ≤ 1000)-字段中的行数和列数。

接下来的n行中的每一行都包含m个符号:“.”表示空单元格,“*”表示无法通过的单元格。

输出

如上所述,将答案打印为矩阵。请参见示例以精确显示输出的格式。

样例输入
Copy
3 3
*.*
.*.
*.*
样例输出
Copy
3.3
.5.
3.3

提示

样例2输入

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

样例2输出

46..3
..732
.6.4.
5.4.3

注释:

在第一个例子中,如果我们假设中央单元格是空的,那么它将被包含到大小为5(交叉)的连通块中。如果任何角落单元格为空,那么它将被包含到大小为3(角落)的连通块中。

来源

[提交][状态]