Chasing Game
Time limit2sMemory limit128 MB
Two players alternately move on a grid trying to reach the other's starting cell first, where landing on the opponent's cell grants a bonus move, and the task is to decide the winner under optimal play.
- Level
Hard8 of 10
- Topics
- Game theory, BFS, Shortest path, Graph
- Solved
- No attempts yet
Problem
Two players, A and B, play a game on an N x N square board. Each player starts on one cell. Every cell is either white or black; black cells cannot be entered. The starting cells of A and B are never black.
On each turn, the current player moves once to one of the four adjacent cells: up, down, left, or right. If that move places the current player on the opponent's current cell, the current player immediately receives one additional move in one of the four directions.
A takes the first turn. The first player to reach the opponent's starting cell wins. Assuming both players use optimal strategies, determine the winner.
Input
The first line contains the number of test cases t (1 <= t <= 10).
Each test case starts with an integer n (1 <= n <= 300), the size of the board. The next n lines describe the board. A and B mark the starting cells of the two players, . marks a white cell, and # marks a black cell.
Output
For each test case, print the winner in input order. Print A if player A wins, and B if player B wins.
Hint
In the first visible test case, no matter which direction A chooses, B can follow so that B's third move lands on A's current cell. B then receives one additional move and reaches A's starting cell first.
In the second visible test case, A can choose a route that avoids meeting B. Without a meeting, A's first-move advantage is enough to win.