P9169 [NOI Qualifier Joint Contest 2023] River-Crossing Pawn

There is a river-crossing pawn on a chessboard that needs to reach the finish line. The pawn can move one cell to the left, one cell to the right, or one cell forward. At the same time, there are two opponent pieces on the board that need to stop the pawn from reaching the finish line. These two pieces move like the general: they can move to an adjacent cell in one of the four directions (up, down, left, right). Therefore, this problem can also be called “General Blocks the River-Crossing Pawn”.

There is a chessboard with $n$ rows and $m$ columns. We use $(i,j)$ to denote the position at row $i$, column $j$. On the board there are some obstacles, one black piece, and two red pieces. The rules of the game are as follows: Red moves first, Black moves second, and they alternate turns. On each Red turn, Red may choose one red piece and move it by one step to an adjacent cell. Specifically, suppose the chosen piece is at $(i,j)$. Then it may move to one of $(i-1,j)$, $(i+1,j)$, $(i,j-1)$, $(i,j+1)$, as long as the destination is inside the board, has no obstacle, and is not occupied by the other red piece. On each Black turn, Black may move its piece by one step in one of three directions. Specifically, suppose the black piece is at $(i,j)$. Then it may move to one of $(i-1,j)$, $(i,j-1)$, $(i,j+1)$, as long as the destination is inside the board and has no obstacle. Before a player takes an action, if any of the following situations occurs, the game ends immediately, and the winner is determined by the following rules (higher priority comes first): - The black piece is on the first row. In this case, Black wins. - The black piece is on the same cell as one of the red pieces. In this case, the player who made the previous move wins. - The current player has no legal move. In this case, the other player wins. Now assume both sides use optimal strategies and will not make moves that are unfavorable to themselves. That is: - If there exists a winning strategy, the player will choose, among all winning strategies, a move that minimizes the maximum number of moves required for the player to win later, no matter how the opponent plays. - If there is no winning strategy, but there exists a strategy that guarantees the player will not lose regardless of how the opponent plays, the player may choose any such non-losing strategy. - If there is no non-losing strategy, the player will choose, among all strategies, a move that maximizes the minimum number of moves required for the opponent to win later, no matter how the opponent plays. If the winner still cannot be determined after $100^{100^{100}}$ turns, the game is considered a tie. Please output the total number of moves made by both sides when the game ends, or determine that the game is a tie.

**This problem has multiple test cases**. The first line contains two integers $\text{id}, T$, representing the test point ID and the number of test cases. In particular, $\text{id}$ is $0$ for the samples. Then follow $T$ test cases. Each test case is given in the following format: The first line contains two positive integers $n, m$, denoting the number of rows and columns of the board. Then follow $n$ lines, each containing a string of length $m$. The $j$-th character of the $i$-th line represents the state of position $(i,j)$ on the board. Among these characters: $\texttt{'.'}$ denotes an empty cell; $\texttt{'\#'}$ denotes an obstacle; $\texttt{'X'}$ denotes the black piece; $\texttt{'O'}$ denotes a red piece. It is guaranteed that there is exactly one black piece, exactly two red pieces, and the black piece is not on the first row.

For each test case, output one line containing a string. If the game is a tie, output $\texttt{"Tie"}$. If Red wins, output $\texttt{"Red t"}$, where $\texttt{t}$ is the total number of moves made by both sides when the game ends. Obviously, this should be an odd number. If Black wins, output $\texttt{"Black t"}$, where $\texttt{t}$ is the total number of moves made by both sides when the game ends. Obviously, this should be an even number. Note: output the string inside the double quotes, without the double quotes.

**[Sample 1 Explanation]** In the first test case, Red has no legal move on the first move, so Black wins. In the second test case, no matter how Red moves on the first move, Black can make the black piece share a cell with a red piece on the next move. In the third test case, no matter how Red moves on the first move, Black can move its piece upward by one cell to achieve victory. In the fourth test case, one red piece cannot move. The other red piece can move within the third row to prevent the black piece from entering the first row. The black piece can also keep moving within the fifth row. If a red piece reaches the fifth row, the black piece can choose to escape from the other side. In the fifth test case, the red piece on the last row can go around from the left side to catch the black piece. Note that the other red piece can move. **[Sample 2 Explanation]** Each test case in this sample satisfies the constraints of one of the test points $5$ to $13$. **[Subtasks]** For all data, it is guaranteed that: $1 \leq T \leq 10$, $2 \leq n \leq 10$, $1 \leq m \leq 10$, and $\text{id}$ equals the test point ID. For each test case, it is guaranteed that there is exactly one black piece, exactly two red pieces, and the black piece is not on the first row. - Test points $1 \sim 4$: It is guaranteed that either the game is a tie, or Red cannot move at the beginning. - Test points $5 \sim 6$: It is guaranteed that $n \geq 4$. It is guaranteed that every cell in row $n-1$ is an obstacle, and there are no obstacles in other rows. It is guaranteed that the black piece is in the first $n-2$ rows, one red piece is in the first $n-2$ rows, and the other red piece is in row $n$. - Test points $7 \sim 9$: It is guaranteed that $m = 1$. - Test points $10 \sim 13$: It is guaranteed that either the game is a tie, or there exists a strategy that can end the game within $9$ moves. - Test points $14 \sim 20$: No special constraints. Translated by ChatGPT 5