P2099 [NOI2007] Deploying Troops

# Description Our intercepted intelligence shows that the enemy is massing forces to attack our important ordnance research institute. Since our army is engaged on multiple fronts and cannot spare large forces for reinforcement, headquarters has decided to improve the odds of victory and reduce casualties and losses through effective pre-battle deployment. The floor plan of the research institute can be viewed as an $N \times M$ matrix. Each $1 \times 1$ cell represents a region, and each region is adjacent only to its four neighbors: up, down, left, and right. Each region falls into one of the following three categories: 1. The region is used for military research (denoted by the letter `O`). 2. A mechanized squad is stationed in the region (denoted by `#`). 3. The region is empty ground (denoted by `.`). Due to limited space, no more than one mechanized squad can be stationed in any $1 \times 1$ cell; having two or more squads in the same cell would severely reduce mobility in battle. Unfortunately, due to inadequate prewar estimates, our defensive deployment is very scattered, which makes it easy for the enemy to capitalize on its specialty in surprise attacks. To ensure absolute security, we decide to use our limited defensive units to surround all important research regions with the minimum number of movement steps. “Surround” means that enemies infiltrating from the boundary of the matrix cannot find any path to reach any research region without encountering resistance from a mechanized squad. Due to internal message-relay authority constraints, in each unit of time, headquarters can issue orders to only one squad among all squads (move 1 cell up, down, left, or right). Because time is short, headquarters hopes to complete the deployment as quickly as possible, and this task is assigned to you. Note: During deployment, squads may enter research regions, but in the final deployment, squads may not be in research regions. Also, at any time, two squads may not occupy the same cell.

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

**该题为提交答案型题目。** 对于每个数据： 第一行 $2$ 个整数 $N,M$。 接下来 $N$ 行，每行包括 $M$ 个字符（均为 `.`、`O`、`#` 之一）。

The first line of each output file contains the time $T$ your solution takes. Then output $T$ lines. In order, output each command. Each line contains $4$ integers $x_1, y_1, x_2, y_2$, indicating moving the squad located at $(x_1, y_1)$ to $(x_2, y_2)$.

If the contestant’s output plan is invalid (overlapping squads during execution, squads moving out of the rectangular boundary, squads occupying research regions in the final plan, research regions not surrounded, etc.), the score is zero. Otherwise, let the time spent by the contestant’s plan be $ans$, and the score is computed as follows: $$ 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