3736 - 保持连通
Description

给出一个 m*n 的迷宫地图,其中 # 表示墙,. 表示空地。保证迷宫是连通的,现在你来把其中 k 个空地变为墙,让剩下的空地仍然是连通的。

Input

第一行:3 个数 m, n, k,中间用空格分隔(1 <= m, n <= 500,k < s),其中 s 为所有空地的数量,m 为行数、n 为列数。
后面 m 行:每行 n 个字符 # 或 .。

Output

输出修改后的迷宫地图,把你要变成墙的地方输出为 X。

Examples

Input

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

Output

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

先统计所有空地的数量 s,然后从任意一个空地开始 BFS(或 DFS),恰好访问 s-k 个空地,最后把未被访问到的空地全部改为 X。这样保留下来的空地一定是连通的。

本题有多解,采用特殊判题(SPJ):任意一组满足“恰好 k 个 X、原有 # 不变、剩余空地连通”的输出均判为正确。

Source
51nod 2662
Tags
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1