P2099 [NOI2007] 调兵遣将

下发文件： 链接：https://pan.baidu.com/s/1JlHZ72eFapfEyqjL_uphoA 提取码：7v4i 由于上传答案文件有大小限制，请尽量使用代码提交= =。

我军截获的情报显示，敌军正在集结兵力试图向我军重要的军械研究所发起进攻。由于我军正处于多线作战的状态，无法抽调大批兵力前去支援，指挥部决定通过有效的战前部署来提高胜率，减少伤亡和损失。 该军械研究所的平面图可以看作是一个 $N\times M$ 的矩阵，每个$1\times 1$ 的格子都表示一个区域，每个区域只与它上下左右的四个区域相邻。每个区域的用途可分为以下3 种之一： 1． 该区域被用于军事研究（用字母 `O` 表示）； 2． 该区域内驻扎有一个机械化中队（用 `#` 表示）； 3． 该区域是空地（用`.`表示）。 由于空间有限，任一个 $1\times 1$ 的格子内都无法驻扎两队以上的机械化中队（包括两队），否则会大大降低战斗时的机动性。 遗憾的是，由于战前估计不足，我军的防御部署显得十分分散，这很容易让敌军所擅长的偷袭战术得逞。为了确保万无一失，我军决定利用为数不多的防御部队以最少的移动步骤将所有重要研究区域都包围起来。所谓的“包围”即从该矩阵边界侵入的敌军找不到任意一条路，使得他们不遭受任何机械化中队的反抗就能到达某研究区域。 由于军队内部的传令权限的限制，每个单位时间指挥部只能向所有中队中的一个中队下达指令（朝上/下/左/右移动 $1$ 格）。由于时间紧迫，指挥部希望能够尽快完成部署，这个任务就交给你来完成。 注意：在部署的过程中军队可以进入研究区域，而在最终的部署结果中军队不可以在研究区域中。另外，在任何时刻，两个军队都不可以在同一个方格中。

无

无

如果选手的输出方案不合法（方案执行过程中出现军队重叠，军队移出矩形边界，最终方案有军队和研究所在同一区域，军队没有包围研究所等），则得零分，否则设选手输出的方案耗时为ans ，则得分按如下计算： $$score= \begin{cases} \ 10&ans \leq A_i\\ \ 1+\left\lfloor\dfrac{ans-B_i}{A_i-B_i}\right\rfloor \times 9&A_i