3736 - 保持连通
描述

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

输入

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

输出

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

样例

输入

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

输出

#XXX
#X#.
X#..
..#.
.#.#
提示

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

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

来源
51nod 2662
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1