P2493 [SDOI2011] Snake

Everyone has probably played the Snake game. Now there is a modified version. As in the traditional Snake game, the snake moves within a play area and eats food, but this modified version has some special rules. Play area: The snake moves in an $R$-by-$C$ grid $A$ and may not leave this grid. The cell in row $i$, column $j$ is denoted $A_{i, j}$. Each cell has an integer weight $w(A_{i, j})$. $0 \leq w(A_{i, j}) \leq 8$. When $w(A_{i, j}) = 0$, $A_{i, j}$ is forbidden to enter; when $w(A_{i, j}) > 0$, $A_{i, j}$ is allowed to enter. Directions: For $P = (X_0, Y_0)$ and $Q = (X_1, Y_1)$, there are four basic directions: - Left (L): if $X_0 = X_1$ and $Y_0 = Y_1 - 1$, then $P$ is to the left of $Q$. - Right (R): if $X_0 = X_1$ and $Y_0 = Y_1 + 1$, then $P$ is to the right of $Q$. - Up (U): if $X_0 = X_1 - 1$ and $Y_0 = Y_1$, then $P$ is above $Q$. - Down (D): if $X_0 = X_1 + 1$ and $Y_0 = Y_1$, then $P$ is below $Q$. Snake: The snake $B$ is a shape occupying several cells. The number of occupied cells is the snake’s length, denoted $m$. From head to tail, the snake is $B_1, B_2, \dots, B_m$. Let $p$ be the snake’s configuration. If $B_i$ is at row $X_i$, column $Y_i$, then $p(B_i) = (X_i, Y_i)$. Initially, $m = 4$, and during movement the following constraints must always hold: - For adjacent parts $B_i$ and $B_{i+1}$ ($1 \leq i < m$), $B_i$ must be in one of the L, R, U, D directions relative to $B_{i+1}$. - For any $B_i$ and $B_j$ ($1 \leq i < j \leq m$), with $p(B_i) = (X_i, Y_i)$ and $p(B_j) = (X_j, Y_j)$, it must hold that $X_i \neq X_j$ or $Y_i \neq Y_j$. In other words, no two parts of the snake’s body may overlap. Food: There is some food in the play area. Each piece of food is on a cell that is allowed to enter, and food pieces do not overlap. Each piece of food can be eaten at most once. Snake movement: If one of the cells $A_{i, j}$ in the L, R, U, or D direction from the head $B_1$ is enterable and there is no food on $A_{i, j}$, the snake may move in that direction, and the new head will be at $A_{i, j}$. Let $p'$ be the new configuration of the snake. Then: - $p'(B_k) = p(B_{k - 1})$ for $2 \leq k \leq m$. - $p'(B_k) = (i, j)$ for $k = 1$. Snake eating: If one of the cells $A_{i, j}$ in the L, R, U, or D direction from the head $B_1$ is enterable and there is food on $A_{i, j}$, the snake may move there to eat. The new head will be at $A_{i, j}$, and the new length is $m' = m + 1$. Let $p'$ be the new configuration. Then: - $p'(B_k) = p(B_{k - 1})$ for $2 \leq k \leq m'$. - $p'(B_k) = (i, j)$ for $k = 1$. Note: After moving or eating, you only need to check whether the resulting configuration satisfies the constraints; you do not need to consider the intermediate process. In other words, it is allowed for a snake whose current configuration is legal to move its head into the previous position of the tail, because the head and tail still do not overlap after the transformation. Time required for movement or eating: Movement or eating consumes time. Let $P$ be the cell of the head before the action, and let $Q$ be the cell of the head after the action. Then the time cost of this action is $|w(P) - w(Q)| + 1$. Before the game begins, the snake’s initial position and all food positions are given. Your task is to make the snake eat all the food in the least possible time.

The first line contains two positive integers $R, C$. Then follow $R$ lines, each containing $C$ digits without spaces. In the $i$-th line, the $j$-th digit is $w(A_{i, j})$. Then follow $4$ lines, each containing $2$ positive integers. In the $i$-th of these lines, the two integers $X_i, Y_i$ indicate $p(B_i) = (X_i, Y_i)$. Then a positive integer $N$ follows, denoting the number of food items. Then follow $N$ lines, each containing $2$ positive integers $i, j$, indicating that there is a piece of food on $A_{i, j}$.

If the snake cannot eat all the food, output `No solution.`. Otherwise, output: - The first line contains an integer, the minimum total time required. - The second line contains a string consisting of characters L, R, U, and D, representing a movement plan for the snake. If multiple solutions exist, output any one of them.

- For $20\%$ of the testdata, $N \leq 1$. - For $30\%$ of the testdata, $R \times C \leq 36$. - For $40\%$ of the testdata, $N \leq 2$. - For $60\%$ of the testdata, $N \leq 3$. - For $100\%$ of the testdata, $N \leq 4$, $R \leq 12$, $C \leq 12$. Translated by ChatGPT 5