Amanda the Amoeba
Contest: European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: graphs, implementation, trees, two pointers

This problem has an attachment. You can use it to simulate and visualize the movements of the amoeba.

Amoeba Amanda lives inside a rectangular grid of square pixels. Her body occupies some of these pixels. Other pixels may be either free or blocked. Amanda moves across the grid using the so-called amoeboid movement. In each step of such a movement, her body first shrinks by one pixel (one pixel of the body is removed and becomes free), and then grows at a different place (one previously-free pixel is added to the body).

To prevent structural damage, Amanda's body always occupies a connected region of pixels, which means that any pair of pixels forming the body can be connected by a sequence of adjacent pixels without ever leaving the body. Two pixels are considered adjacent if they share a common side (each pixel has at most 4 neighbours). The body remains connected even during the movement, including the moment after removing a pixel and before adding another one.

Your task is to help Amanda find her way around. Given her initial position and desired final position, suggest a sequence of valid moves leading from the former to the latter.

Illustration of sample $$$1$$$: The filled shape is the initial position, the dotted region is the final position.

Input format:
The first line contains two integers $$$r$$$ and $$$c$$$ ($$$1\le r,c \le 50$$$) — the size of the rectangular grid in pixels.

The next $$$r$$$ lines contain $$$c$$$ characters each, describing the initial position of Amanda. Each of those characters is either a dot $$$\texttt{.}$$$ denoting a free pixel, an asterisk $$$\texttt{*}$$$ denoting Amanda's body, or an $$$\texttt{X}$$$ denoting a blocked pixel which may never be occupied.

The next line is empty.

The next $$$r$$$ lines describe the desired final position in the same format as the initial position.

It is guaranteed that:

- The number of pixels forming Amanda's body is the same in both positions, and it is at least 2.
- The body of Amanda is connected in the initial position.
- The body of Amanda is connected in the final position.
- The blocked pixels do not change between the descriptions of the initial and final position, their placement is exactly the same in both positions.

Output format:
Print $$$\texttt{YES}$$$ if it is possible for Amanda to go from the initial position to the final one. Otherwise, print $$$\texttt{NO}$$$.

If it is possible, on the next line print one integer $$$m$$$ ($$$0\le m\le 10\,000$$$) — the number of moves to execute.

The following $$$m$$$ lines must contain four integer coordinates each: $$$i_1$$$, $$$j_1$$$, $$$i_2$$$, $$$j_2$$$ ($$$1\le i_1,i_2\le r$$$, $$$1\le j_1,j_2\le c$$$). These four coordinates specify one move, meaning that the pixel at $$$i_1$$$-th row and $$$j_1$$$-th column is first removed from the body. Then, $$$(i_2,j_2)$$$ must designate a different location where one pixel is added.

The sequence should consist only of valid moves and after the last move, Amanda's body should occupy the desired final position.

If there are multiple solutions, print any of them.

Under the assumptions of this problem, it can be proven that if it is possible for Amanda to go from the initial position to the desired final one, then it is possible to do it with at most $$$10\,000$$$ moves.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, Amanda executes 5 moves to reach the final position, as shown in the figure below.

Example input:
5 8
.******.
**.X**..
*******.
**.X**..
.******.
.******.
...X****
.*******
...X****
.******.

Example output:
YES
5
3 1 3 8
2 1 2 8
4 1 4 8
2 2 4 7
4 2 2 7

Example input:
2 5
*.X..
**X..
..X**
..X*.

Example output:
NO

Editorial:
To solve this problem, we first find a path $$$P_{AB}$$$ connecting two pixels $$$A$$$ and $$$B$$$ such that
• Pixel $$$A$$$ is a part of the initial position.
• Pixel $$$B$$$ is a part of the final position.
• All inner pixels of $$$P_{AB}$$$ (let us denote their sequence as $$$Q_{AB}$$$) are free pixels, neither inside the initial position nor the final one.
Note that it is generally allowed to select two neighbouring pixels or even having $$$A=B$$$, in which case $$$Q_{AB}$$$ will be empty. For the solution to work, it is not important how such a path is found, one possible way is to find the shortest path between the initial and final position.
If no such path exists, the problem has no solution, as it means the initial and final position are completely separated by blocked cells. Otherwise, the final position is reachable and the problem has a solution, which will be proven by describing its construction.
As the next step, we will construct a tree $$$T_A$$$ rooted in pixel $$$A$$$ and containing all pixels of the initial position (and no other pixels), and also a tree $$$T_B$$$ rooted in pixel $$$B$$$ and containing all pixels of the final position (and only them). Again, it is not important how the trees look like, as far as they contain all appropriate pixels. It is easy to construct them using either DFS or BFS.
The solution then consecutively removes pixels of $$$T_A$$$ bottom-up, starting from leaves and proceeding to parents when they become leaves. Such removed pixels are first added to fill the sequence $$$Q_{AB}$$$, and then to tree $$$T_B$$$ top-down, starting with $$$B$$$ and going to lower nodes after their parents were added. In the end, pixels of $$$Q_{AB}$$$ need to be removed (and added to the bottom of $$$T_{B}$$$). After that, the amoeba will occupy the exact final position.
There is one more important issue to cope with. The trees $$$T_A$$$ and $$$T_B$$$ are not necessarily disjoint, which means that some (or even many) pixels may appear in both. While removing pixels from $$$T_A$$$ and adding them to $$$T_B$$$, the following situations may occur:
• Some pixel should be removed from $$$T_A$$$ but we know it is also part of $$$T_B$$$ and has not been added yet. In this case, the algorithm proceeds just normally, removing the pixel. It will later be added again to the body, which adds to the total number of moves, but there is no requirement to minimize that number.
• Some pixel should be added to $$$T_B$$$ but it is still part of the body, as it was not yet removed from $$$T_A$$$. In such a case, the pixel is skipped (and stays a part of the body to keep it connected) and it has to be marked as such. When the algorithm later proceeds to that pixel as part of $$$T_A$$$, it must not be removed anymore, and the algorithm proceeds to other pixels in $$$T_A$$$.
These steps keep the amoeba connected at all times, and in the end, all pixels of $$$T_B$$$ are occupied, which means reaching the final position. Although the algorithm may remove some pixels and then add the same pixels again, this happens at most once for each of the pixels. In fact, each pixel is removed at most once and also added at most once, which means the maximal number of steps produced by the algorithm is limited by the total number of pixels in the pixture, $$$r\cdot c$$$, which is way below the required limit.