Background

NOIP2018 Original Simulation Question T3

Difficulty comparable to NOIP DAY1 T3 or DAY2 T2

Everyone has played the snake game, but different versions have different rules. Let's introduce the PION Snake.

Problem Description

Representation Method:

In this problem, the snake exists in an n-row by m-column rectangle, where '.' represents an empty space, '#' represents the snake's body, '@' represents the snake's head, and '&' represents food.
For example, Figure 1 represents a 5x6 rectangle with one snake of length 7 and two pieces of food.

Basic Rules:

1. The snake's head moves one cell per second, and the body follows naturally. W represents up, S represents down, A represents left, and D represents right.
2. Each time the snake eats food, its length increases by one, which is reflected at the location of the food. You can think of eating food as the food becoming the new head, and the previous head becoming part of the body, without moving that second.
3. If the snake dies, its entire body (including the head) turns into food.
4. The PION Snake's head will die if it touches its own body or another snake's body.
5. The snake's head will also die if it hits the boundary, except when it is exactly on the boundary.
6. If an operation causes the snake's head to move in the opposite direction and overlap with its body, the snake will die.
7. If two snake heads collide, the one that initiates the collision dies.
8. The snakes move in order from the smallest to the largest number (the meaning of the numbering is described below).

Input Format

The first line contains three numbers \( n, m, k \) representing the \( n \times m \) rectangle and \( k \) operations.
The next \( n \) lines, each containing \( m \) characters, represent the map.
The following \( c \) lines (note: there are as many lines as there are snakes), each containing \( k \) characters, represent \( k \) operations (if a snake dies from an operation, ignore subsequent operations).

We number the snakes: based on the coordinates of each snake's head from smallest to largest (coordinates closer to the top are smaller, and if equal, coordinates closer to the left are smaller).

For example, in Figure 3, the coordinates of the two snake heads are (4,3) and (3,7), so the longer snake is numbered 2, and the shorter snake is numbered 1.

Output Format

\( c+1 \) lines, output the length and number of each snake after \( k \) operations; the first number on each line is the length, and the second number is the number.
The last line outputs the total number of remaining food.

Note: Output is sorted by length from largest to smallest (if lengths are the same, sort by number from smallest to largest), and dead snakes have a length of 0.

Sample Input and Output

Input Sample #1

5 7 6
.&...&.
..##@..
.&...&.
..##@..
.&...&.
DWAAAA
WDDDDD

Output Sample #1

5 1
0 2
7

Input Sample #2

9 9 4
.........
.#######.
.......#.
.@#.&@.#.
&.#.&&.#.
&&######.
.&.......
..@####..
.........
ASSD
ASDD
WASD

Output Sample #2

22 1
4 2
0 3
6

Notes

Sample Explanation:

Figures 5 and 6 show the state of the map from the 0th second onwards. Please refer to the figures for understanding (there is a small error in Figure 4 of Sample 2).

Data Range:

10% of the data satisfies \( n, m \leq 5, c = 1, k \leq 3 \)

30% of the data satisfies \( n, m \leq 10, c \leq 2, k \leq 5 \)

50% of the data satisfies \( n, m \leq 50, c \leq 5, k \leq 20 \)

70% of the data satisfies \( n, m \leq 100, c \leq 7, k \leq 50 \)

100% of the data satisfies \( n, m \leq 200, c \leq 20, k \leq 100 \), and the snakes in the map will not cause confusion (for any snake head, there is at most one body part connected to it, and the body part is at most a two-block segment). The data guarantees that the relationship between the snake's body and head can be determined, and there will be no multiple solutions for the snake's body shape.

见题面 Input 部分

见题面 Output 部分