#P50486. 「NOI2007」 调兵遣将

「NOI2007」 调兵遣将

Cannot parse: undefinedms error parsing time

题目描述

我军截获的情报显示,敌军正在集结兵力试图向我军重要的军械研究所发起进攻。由于我军正处于多线作战的状态,无法抽调大批兵力前去支援,指挥部决定通过有效的战前部署来提高胜率,减少伤亡和损失。

该军械研究所的平面图可以看作是一个 N×MN \times M 的矩阵,每个 1×11 \times 1 的格子都表示一个区域,每个区域只与它上下左右的四个区域相邻。每个区域的用途可分为以下 33 种之一:

  • 该区域被用于军事研究(用字母O表示);
  • 该区域内驻扎有一个机械化中队(用#表示);
  • 该区域是空地(用.表示)。

由于空间有限,任一个 1×11\times 1 的格子内都无法驻扎两队以上的机械化中队(包括两队),否则会大大降低战斗时的机动性。
遗憾的是,由于战前估计不足,我军的防御部署显得十分分散,这很容易让敌军所擅长的偷袭战术得逞。为了确保万无一失,我军决定利用为数不多的防御部队以最少的移动步骤将所有重要研究区域都包围起来。所谓的“包围”即从该矩阵边界侵入的敌军找不到任意一条路,使得他们不遭受任何机械化中队的反抗就能到达某研究区域。
由于军队内部的传令权限的限制,每个单位时间指挥部只能向所有中队中的一个中队下达指令(朝上/下/左/右移动 11 格)。由于时间紧迫,指挥部希望能够尽快完成部署,这个任务就交给你来完成。
注意:在部署的过程中军队可以进入研究区域,而在最终的部署结果中军队不可以在研究区域中。另外,在任何时刻,两个军队都不可以在同一个方格中。

输入格式

该题为提交答案型试题,所有输入数据 surround1.in~surround10.in 在附加文件中。
对于每个数据:
第一行包括 2 个整数 N,MN , M ,接下来 NN 行,每行包括 MM 个字符( ., O# )。

输出格式

针对给定的 1010 个输入文件 surround1.in~surround10.in ,你需要分别提交你的输出文件 surround1.out~sourround10.out 。 每个输出文件的第一行,包括你的答案所花费的时间 TT 。接下来 TT 行,按顺序输出每条命令,每行包括 44 个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2 ,表示将位于 (x1,y1)(x_1,y_1) 的部队移向 (x2,y2)(x_2,y_2)

样例

5 5
..##.
#...#
#OOO#
#..O#
.###.
1
2 1 2 2

数据范围与提示

评测方法

如果选手的输出方案不合法(方案执行过程中出现军队重叠,军队移出矩形边界,最终方案有军队和研究所在同一区域,军队没有包围研究所等),则得零分,否则设选手输出的方案耗时为 ansans ,则得分按如下计算:

$$f(x)= \begin{cases} 10 & (ans \le A_i)\\ 1+\left\lfloor (\frac{ans-B_i}{A_i-B_i})^2 \times 9 \right\rfloor & (A_i B_i) \end{cases} $$

你如何测试自己的输出

我们提供 surround_check 这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是: surround_check <输入文件名> <输出文件名>
在你调用这个程序后, surround_check 将根据你给出的输入和输出文件给出测试的结果,其中包括:

  • 非法退出:未知错误;
  • overlap:出现军队重叠,或最终方案有军队和研究所在同一区域;
  • outside:军队移出矩形边界;
  • move error:移动一个不存在的军队,或移动距离不只一格;
  • not surround:军队没有包围所有研究所;
  • time not match:输出文件中移动步数与输出答案不符;
  • yes:输出可接受,将进行下一步的评分。