P6806 [CEOI 2020] Chess World

1.3s, 64MB

Chess World is a board with $R$ rows and $C$ columns, where $R \geq C$. All rows are numbered from $1$ to $R$, and all columns are numbered from $1$ to $C$. In Chess World, there are five types of pieces: pawn, rook, bishop, queen, and king. Unlike the real world, chivalry has died in Chess World, so there are no knights. In Chess World, each piece can make one move according to the following rules: - A pawn can only move one step toward increasing row numbers (from row $r$ to row $r+1$), and its column does not change. - A rook can move only horizontally or vertically. - A bishop can move only diagonally. - A queen can move horizontally, vertically, or diagonally. - A king can move to any of the eight adjacent squares. To help you understand, the figure below shows the legal move range for each piece. Here, X represents squares that the piece can move to.  Recently, many strange things have happened in Chess World: some pieces may be hijacked by an unknown force and then disappear from Chess World. In this situation, all pieces want to reach their destinations as soon as possible. They also want to know, among all ways that use the minimum number of moves, how many such ways there are. Two ways are considered different if and only if there exists at least one move where the square passed through is different. In this problem, you need to solve the following task: a piece starts from column $c_1$ in row $1$, and needs to reach column $c_R$ in row $R$. You are given the type of the piece and the values of $c_1, c_R$. You need to compute the minimum number of moves needed, and the number of ways to reach the destination with the minimum number of moves.

The first line contains three integers $R, C, Q$, representing the number of rows, the number of columns, and the number of queries. The next $Q$ lines each contain a letter $T$, representing the piece type, and two integers $c_1, c_R$, meaning the start is at column $c_1$ in row $1$, and the end is at column $c_R$ in row $R$. The mapping between letters and piece types is as follows: | Letter | Piece Type | | ------------ | ---------- | | $\texttt{P}$ | Pawn | | $\texttt{R}$ | Rook | | $\texttt{B}$ | Bishop | | $\texttt{Q}$ | Queen | | $\texttt{K}$ | King |

For each query, output two integers. The first integer is the minimum number of moves needed to go from the start to the end. The second integer is the number of ways to go from the start to the end using the minimum number of moves. Since the number of ways can be very large, output it modulo $10^9+7$. In particular, if it is impossible to reach the destination from the start, output one line `0 0`.

All test cases satisfy: $1 \leq Q \leq 1000$, $2 \leq C \leq 1000$, $C \leq R \leq 10^9$, $T \in \{\texttt{P},\texttt{R},\texttt{Q},\texttt{B},\texttt{K}\}$, $1 \leq c_1, c_R \leq C$. The constraints for each subtask are as follows: | Subtask ID | Score | Constraints | | ---------- | ----- | -------------------------------------------- | | $1$ | $0$ | Sample | | $2$ | $8$ | $T \in \{\texttt{P},\texttt{R},\texttt{Q}\}$ | | $3$ | $15$ | $T=\texttt{B}$, $C, R \leq 100$ | | $4$ | $22$ | $T=\texttt{B}$ | | $5$ | $5$ | $T=\texttt{K}$, $C, R \leq 100$, $Q \leq 50$ | | $6$ | $8$ | $T=\texttt{K}$, $C, R \leq 100$ | | $7$ | $15$ | $T=\texttt{K}$, $C \leq 100$ | | $8$ | $20$ | $T=\texttt{K}$ | | $9$ | $7$ | No special constraints | Translated by ChatGPT 5