Background

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.

Output Format

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)$.

5 5
..##.
#...#
#OOO#
#..O#
.###.

1
2 1 2 2

Hint

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<ans \leq B_i\\ \ 1&B_i<ans\\ \end{cases}$$

For each dataset, there are two scoring parameters $A_i$ and $B_i$, with $A_i < B_i$ guaranteed.

Translated by ChatGPT 5