← 返回题目列表

Codeforces · 616/C

C. 迷宫

中文机器翻译题面 查看原题

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

我们将连接组件称为任何不可扩展的单元集,其中任何两个单元都通过相邻单元的路径连接。这是连接组件的典型众所周知的定义。

对于每个不可通过的单元格 (x, y),想象它是一个空单元格(所有其他单元格保持不变),并找到包含 (x, y) 的连通分量的大小(单元格数量)。您应该独立地为每个不可通过的单元格执行此操作。

答案应打印为 n 行 m 列的矩阵。第 i 行的第 j 个符号应该是“.”。如果单元格在开始时为空。否则,第 i 行的第 j 个符号应包含唯一的数字 ---- 答案模 10。打印的矩阵应不带任何空格。

为了使输出更快,建议将输出构建为长度为 m 的 n 个字符串数组,并将其打印为行序列。这比逐个字符写要快得多。

由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在C++中更喜欢使用scanf/printf而不是cin/cout,在Java中更喜欢使用BufferedReader/PrintWriter而不是Scanner/System.out。

输入

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

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

输出

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

示例

输入 #1

3 3
*.*
.*.
*.*

输出 #1

3.3
.5.
3.3

输入 #2

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

输出 #2

46..3
..732
.6.4.
5.4.3

注意

在第一个示例中,如果我们假设中心单元格是空的,那么它将包含在尺寸为 5(十字)的组件中。如果任何角单元为空,则它将包含在尺寸为 3(角)的组件中。