题目背景

数据以及checker下载

题目描述

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

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

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

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

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

评分

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

• 除了把输入文件中的任意多个字母.修改成字母X（即被灌木堵塞）外，输出的地图必须和输入地图完全一样。

• 输出的地图必须符合在上文中提及的迷宫的所有性质。

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

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

请注意如果你答案是有效的，但根据上述公式你的得分仍然是$0$分，则在评分系统中，现实的结果将会是'Wrong Answer'。

输入格式

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

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

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

第$1$行： $1 : \ \ m \ n \ k$

第$1+i\ (1 \leqslant i \leqslant m)$行： 网格中的第$i$行，它是一个长度为$n$的字符串，包含以下的字符（中间没有空格）：

• .： 一个空格，

• #： 一块岩石。

输出格式

第$i\ (1 \leqslant i \leqslant m)$行： 迷宫中的第$i$行（种植了树木的花园）。它是一个长度为$n$的字符串，包含以下字母（中间没有空格）：

* . ： 一个空格，

* #： 一块岩石，

* X： 一个灌木（注意字母X必须为大写字母）。

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

.X.X#
.#..#
...#X
XX..#

//这是其中一个有效的输出

提示

样例输出是其中一个有效的输出。

对于这个输出，因为$l=4$个小孩能够这个迷宫中，所以这个解答能够得到$10 \cdot 4 / 5 = 8$分。小孩能够躲藏的方格如下以O所示：

OXOX#
.#.O#
...#X
XX.O#

以下的三个输出都不是有效的输出：

.XXX#    ...X#    XXXX#
.#XX#    .#.X#    X#XX#
...#.    ...#X    ..X#X
XX..#    XXXX#    ..XX#

在最左边的输出中，左上角的空格和最右列（位于右下方）的空格之间并没有一条简单路径。

在其他的两个输出中，对于任意两个空格之间都恰有两条简单路径相连。

限制条件

$1 \leqslant m,n \leqslant 1024$

checker使用方法

在checker目录下，在终端输入./checker in out out

使用此命令将返回out对于in的得分

其中in为题目提供的输入文件，out为你对于该输入文件给出的答案文件

此时将有以下几种返回情况：

1. Map Error 1 ：地图大小不正确。

2. Map Error 2 ：地图上有'.','X','#'以外的字符。

3. Map Error 3 ：原地图有岩石未出现在所给的地图上或出现了额外的岩石。

4. Map Error 4 ：所给的地图出现了超过一个联通块。

5. Map Error 5 ：所给的地图不是一个迷宫。

6. points a Standard answer is b,your answer is c. ：该测试点你获得了a分，标准答案能藏b个小孩而你的答案能藏c个。

由@zhouyonglong提供SPJ