P4944 PION Snake

NOIP 2018 original mock problem T3. Difficulty similar to NOIP Day 1 T3 or Day 2 T2. Everyone has played Snake, right? Of course, different versions have different rules. Below is an introduction to PION Snake.

 ***Notation:*** In this problem, the snakes live in a rectangle with $n$ rows and $m$ columns. `.` represents empty ground, `#` represents the snake body, `@` represents the snake head, and `&` represents food. For example, Figure 1 shows a $5*6$ rectangle with one snake. The snake has length $7$, and there are two pieces of food. ***Basic rules:*** 1. Each second, a snake head moves by one cell, and the body follows naturally. Use `W` for up, `S` for down, `A` for left, and `D` for right. 2. Each time a snake eats one piece of food, its length increases by $1$. The increased length appears at the cell where the food was. You can understand “eating food” as: the food becomes the new head, the previous head becomes part of the body, and the snake does not move during this second. For example, the three sub-figures in Figure 2 show the situations at the first second, the second second, and the third second. 3. If a snake dies, its entire body (including the head) will all turn into food. 4. If a snake head touches its own body or another snake’s body, it dies. For example, the three sub-figures in Figure 3 show the process where the second snake crashes into another snake’s body and dies. 5. If a snake head hits the boundary, it also dies, but merely being exactly on the boundary does not. For example, in the second sub-figure of Figure 4, although the head is on the boundary, it is only exactly on it. If you perform `D` at this time, the snake will die; if you perform `W` or `S`, it will not. 6. If an operation makes the snake head move in the opposite direction, then later, if it overlaps with its body, the snake will also die (for example: if in the first sub-figure of Figure 2 you use operation `A`, the snake will die and become three pieces of food on the spot. You may also think of it as the snake not moving next second and committing suicide). 7. If two snakes’ heads collide, the one that actively撞上 (runs into the other) dies. 8. Snakes move in increasing order of their indices (the meaning of indices is explained below).

The first line contains three integers $n,m,k$, where $n*m$ is the rectangle, and $k$ is the number of operations. Next $n$ lines each contain $m$ characters, describing the map. Then follow $c$ lines (note: there are as many lines as there are snakes in the map). Each line contains $k$ characters, representing $k$ operations (if a snake dies after performing some operation, ignore the remaining operations). We index the snakes as follows: sort all snakes by the coordinates of their heads from small to large, and assign indices $1,2,\ldots,c$ (a smaller row coordinate means smaller; if rows are equal, a smaller column coordinate means smaller). For example, in the first sub-figure of Figure 3, the head coordinates of the two snakes are $(4,3)$ and $(3,7)$, so the longer snake is indexed as $2$, and the shorter snake is indexed as $1$.

Output $c+1$ lines. After $k$ operations, output the length and the index of each snake. In each line, the first number is the length, and the second number is the index. In the last line, output the total number of remaining pieces of food. Note: output should be sorted by length from large to small (if lengths are equal, sort by index from small to large). The length of a dead snake is $0$.

***Sample explanation:***  Figures 5 and 6 show the map state at each second starting from second $0$. Please read the figures to understand (there is a small mistake in Figure 4 of Sample 2). ***Constraints:*** $10\%$ of the testdata satisfies $n,m\leq 5,c=1,k\leq3$. $30\%$ of the testdata satisfies $n,m\leq 10,c\leq 2,k\leq 5$. $50\%$ of the testdata satisfies $n,m\leq 50,c\leq 5,k\leq 20$. $70\%$ of the testdata satisfies $n,m\leq 100,c\leq 7,k\leq 50$. $100\%$ of the testdata satisfies $n,m\leq 200,c\leq 20,k\leq 100$, and the snakes in the figure will not cause ambiguity (for any snake head, at most one body block is connected to it, and each body block has at most two adjacent body blocks). The testdata also guarantees that the correspondence between each snake’s body and head can be determined, and the snake body shape will not have multiple valid interpretations. Translated by ChatGPT 5