← 返回题目列表

Codeforces · 377/A

A. 迷宫

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

帕维尔喜欢网格迷宫。网格迷宫是一个 n × m 的矩形迷宫,其中每个单元格要么是空的,要么是一面墙。仅当两个单元格都是空的并且有公共边时,您才可以从一个单元格转到另一个单元格。

Pavel 画了一个网格迷宫,所有空单元格形成一个连接区域。也就是说,您可以从任何空单元格转到任何其他单元格。帕维尔不喜欢他的迷宫的墙太少。他想将恰好 k 个空单元格变成墙壁,以便所有剩余的单元格仍然形成一个连接的区域。帮助他。

输入

第一行包含三个整数n、m、k(1 ≤ n、m ≤ 500、0 ≤ k < s),其中n和m是迷宫的高度和宽度,相应地,k是Pavel想要添加的墙的数量,字母s代表原始迷宫中空单元的数量。

接下来的 n 行每行包含 m 个字符。他们描述了原来的迷宫。如果一行上的字符等于“.”,则相应的单元格是空的,如果该字符等于“#”,则该单元格是一堵墙。

输出

打印 n 行,每行包含 m 个字符:符合 Pavel 要求的新迷宫。将您转换成墙壁的空单元格标记为“X”,其他单元格必须保持不变(即“.”和“#”)。

保证存在解。如果有多个解决方案,您可以输出其中任何一个。

示例

输入 #1

3 4 2
#..#
..#.
#...

输出 #1

#.X#
X.#.
#...

输入 #2

5 4 5
#...
#.#.
.#..
...#
.#.#

输出 #2

#XXX
#X#.
X#..
...#
.#.#