在安大略省南部，许多玉米农场主会像图中所示那样制作玉米秆迷宫。这些迷宫是在秋季谷物收割后制作的。现在还有时间让你为 2010 年设计一个最棒的迷宫。

田地里除了少数障碍物（如树木、建筑物等）外，其余地方都覆盖着玉米秆，这些地方玉米无法生长。极高的玉米秆构成了迷宫的墙壁。路径是在方形网格上通过压倒 $1\text{m}$ 平方区域的玉米秆而创建的。边缘上的一个网格方块是入口，另一个网格方块是迷宫的核心。

杰克每年都会参观玉米迷宫，并且已经非常擅长快速找到从入口到核心的路径。你正在设计一个新的迷宫，你的工作是确定压倒哪些玉米秆，以最大化杰克必须经过的方块数量。

评分系统将确定哪个方块是入口（周长上唯一的入口），哪个方块是核心（杰克必须走最远距离才能到达的方块）。

矩形田地的地图以文本形式表示；例如，一个 $6\text{m} \times 10\text{m}$ 且有八棵树的田地可能表示为：

##X#######
###X######
####X##X##
##########
##XXXX####
##########

符号 # 代表覆盖着直立玉米秆的方块，X 代表有障碍物（如树木）且无法被压倒形成路径的方块。

田地通过压倒被玉米占据的方块转化为迷宫。一个被压倒的方块（入口）必须位于田地的边缘。其他被压倒的方块必须位于内部。目标是最大化从入口到核心的最短路径，以杰克必须经过的被压倒方块的数量来衡量，包括入口和核心。只有当两个方块都被压倒且它们共享一条边时，才可能从一个方块移动到另一个方块。

在你的提交中，被压倒的方块应由句点 . 标识。被压倒的方块中必须恰好有一个位于周长上。例如：

#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########

下面仅为说明起见，我们标记了入口 E，核心 C，并使用 + 标记路径的其余部分。路径长度为 12。

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

文件夹 /home/ioi2010-contestant/maze 包含几个名为 field1.txt、field2.txt 等的文本文件，其中包含玉米田的地图。你需要将它们复制到名为 maze1.txt、maze2.txt 等的文件中，并通过将一些 # 符号替换为句点来将它们转换为有效的迷宫。

说明：评分服务器的公开测试将为任何有效的解决方案（无论路径长度如何）每个子任务奖励 1 分。评分服务器的发布测试将奖励剩余的分数。该任务的总分将四舍五入到 0 到 110 之间的最接近整数。

子任务 1 [最高 11 分]

上述田地（大小为 $6 \times 10$）可在文件 field1.txt 中找到。为该田地创建一个名为 maze1.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/20}$ 中的较小值。注意，示例解决方案得分为 3.98 分。

子任务 2 [最高 11 分]

文件 field2.txt 代表一个 $100 \times 100$ 的田地。为该田地创建一个名为 maze2.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/4000}$ 中的较小值。

子任务 3 [最高 11 分]

文件 field3.txt 代表一个 $100 \times 100$ 的田地。为该田地创建一个名为 maze3.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/4000}$ 中的较小值。

子任务 4 [最高 11 分]

文件 field4.txt 代表一个 $100 \times 100$ 的田地。为该田地创建一个名为 maze4.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/4000}$ 中的较小值。

子任务 5 [最高 11 分]

文件 field5.txt 代表一个 $100 \times 100$ 的田地。为该田地创建一个名为 maze5.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/5000}$ 中的较小值。

子任务 6 [最高 11 分]

文件 field6.txt 代表一个 $11 \times 11$ 的田地。为该田地创建一个名为 maze6.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/54}$ 中的较小值。

子任务 7 [最高 11 分]

文件 field7.txt 代表一个 $20 \times 20$ 的田地。为该田地创建一个名为 maze7.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/33}$ 中的较小值。

子任务 8 [最高 11 分]

文件 field8.txt 代表一个 $20 \times 20$ 的田地。为该田地创建一个名为 maze8.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/95}$ 中的较小值。

子任务 9 [最高 11 分]

文件 field9.txt 代表一个 $11 \times 21$ 的田地。为该田地创建一个名为 maze9.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/104}$ 中的较小值。

子任务 10 [最高 11 分]

文件 fieldA.txt 代表一个 $200 \times 200$ 的田地。为该田地创建一个名为 maze10.txt 的迷宫，使其从入口到核心的最短路径长度为 $P$。该子任务的得分将是 11 和 $10^{P/7800}$ 中的较小值。

实现细节

• 这是一个仅输出（output-only）的任务。
• 实现文件夹：/home/ioi2010-contestant/maze/
• 参赛者需提交：maze1.txt、maze2.txt、maze3.txt、maze4.txt、maze5.txt、maze6.txt、maze7.txt、maze8.txt、maze9.txt、maze10.txt。
• 参赛者接口：无
• 评测接口：无
• 示例评测程序：grader.c 或 grader.cpp 或 grader.pas
• 示例评测程序输入：grader.in.1、grader.in.2 等。 说明：实现文件夹包含非常简单的解决方案 maze1.txt、maze2.txt 等。将它们复制到 grader.in.1、grader.in.2 等以进行测试。
• 示例评测程序输入的预期输出：如果输入是子任务 $N$ 的有效迷宫，示例评测程序将输出 OK N P，其中 $P$ 是路径长度。
• 编译并运行（命令行）：runc grader.c 或 runc grader.cpp 或 runc grader.pas
• 编译并运行（gedit 插件）：编辑评测程序时按 Control-R。
• 提交（命令行）：submit maze1.txt 或 submit maze2.txt 等。实现文件夹中的所有 .txt 文件都将被提交，无论在提交命令中指定了哪一个。
• 提交（gedit 插件）：编辑任何 .txt 文件时按 Control-J。