A5858. 「IOI2017」诺鲁孜节

再过几天就是诺鲁孜节了（波斯人的新年），爷爷邀请他的全家人到他的花园来聚会。在众多的宾客中有 $k$ 个小孩。为了让这些孩子们在聚会中更开心，爷爷打算让他们玩一个捉迷藏的游戏。

整个花园可以看成一个有 $m\times n$ 个方格的网格。其中有一些（或许没有）方格被岩石堵住了，而剩下的方格就称为**空格**。如果两个格子共享同一条边，我们就称这两个格子是**邻居**。因此，每一个方格最多有 $4$ 个邻居：两个水平方向的和两个垂直方向的。爷爷想把花园变成一个迷宫。为达此目的，他会在花园中的一些空格上种植灌木来堵住他们。而这些被灌木丛堵住的方格就不再是空格了。

一个迷宫必须具有下面所述的性质。在迷宫中的任意一对空格 $a$ 和 $b$ 之间都只会恰有唯一的一条简单路径相连。而这条由 $a$ 到 $b$ 的简单路径就是一个从空格 $a$ 开始并以空格 $b$ 结束的空格序列，序列中所有的方格必须是不同的，而且每两个相连的方格都是邻居。

一个小孩能够躲藏的方格当且仅当这个方格是空格，而且它恰有唯一一个邻居是空格。同一个空格内只能躲藏一个小孩。

题目会给出整个花园的地图作为输入文件。你的任务就是帮助爷爷构造一个能够躲藏尽量多小孩的迷宫。

这是一个提交答案型的题目，而且它有部分分。题目会给出 $10$ 个描述爷爷花园的输入文件，你可以在本题的附加文件中找到它们。对于每个输入文件你应该提交一个含有迷宫的地图作为输出文件。我们会根据你提交的每个输入文件中的迷宫能够躲藏的小孩数目来给出你的分数。

这道题目你不需要提交任何源代码。

每个输入文件都描述了一个表示整个花园的网格，我们也会给出爷爷邀请的小孩数目 $k$。格式如下：

- 第 $1$ 行：$n\ m\ k$
- 第 $1 + i(1 \leq i \leq m)$ 行：网格中的第 $i$ 行，它是一个长度为 $n$ 的字符串，包含以下的字符（中间没有空格）：
- .：一个空格。
- #：一块岩石。

- 第 $i(1 \leq i \leq m)$ 行：迷宫中的第 $i$ 行 (种植了灌木的花园)。它是一个长度为 $n$ 的字符串，包含以下的字符（中间没有空格）：
- .：一个空格。
- #：一块岩石。
- X：一个灌木（注意字母 X 必须为大写字母）。

**关于输出文件的评分：**

一个**有效**的输出文件必须符合下列所有的条件：

- 除了把输入文件中的任意多个字符 . 修改成字母 X（即被灌木堵塞）外，输出的地图必须和输入地图完全一样。
- 输出的地图必须符合在上文中提及的迷宫的所有性质。

对于某一个测试数据，如果你的输出不是有效的，你的这个测试数据的得分将会是 $0$。反之，你的得分是 $\min(10, 10\cdot l/k)$，向下取值至小数后二位，这里的 $l$ 是指你输出的迷宫中能够最多藏着的小孩数目，而 $k$ 则表示在输入文件中题目要求你躲藏的小孩数目。对于一个测试数据，你能够得到 $10$ 分，当且仅当你的输出是一个能够躲藏 $k$ 个或更多个小孩的迷宫。

对于每组测试数据都存在一个能得到 $10$ 分的答案。

需要注意的是，即使你的答案是有效的，但根据上述公式，你的得分仍然可能是 $0$ 分，此时评测返回的结果为 Wrong Answer。

- $1 \leq m, n \leq 1024$。