A Knightly Pursuit
Time limit1sMemory limit128 MB
Given board size and starting squares for a pawn and a knight, decide whether the knight can win, force a stalemate, or loses, and report the minimum knight moves.
- Level
Medium7 of 10
- Topics
- BFS, Simulation, Game theory, Implementation
- Solved
- No attempts yet
Problem
In chess, each piece moves around an board in a way defined by its type. The object of the game is to capture opposing pieces by landing on their square, and eventually to trap the king.
In this variant we use a board of variable size with only pieces on it:
- A white pawn that advances relentlessly toward the top row of the board, one square straight up per move.
- A black knight that can move from its current square in up to eight ways: two squares up or down and one square left or right, or one square up or down and two squares left or right. The knight must always remain on the board; any move that would take it off the board is disallowed.
In the diagram below the knight's square is marked and the squares it can move to are marked to :
. . . . . . .
. . 8 . 1 . .
. 7 . . . 2 .
. . . K . . .
. 6 . . . 3 .
. . 5 . 4 . .
. . . . . . .
The pawn moves first; after that the knight and the pawn move alternately. On each of its turns the knight tries to land either on the square currently occupied by the pawn (a win) or on the square immediately above the pawn (a stalemate). If the pawn reaches the top row of the board, the game ends immediately and the knight loses (a loss).
For each game, determine whether the knight can win and, if it can, the minimum number of knight moves needed. If the knight cannot win, determine whether it can force a stalemate and, if it can, the minimum number of knight moves needed. If the knight can neither win nor force a stalemate, determine the number of moves the knight makes before the pawn wins.
Input
The first line contains a positive integer , the number of games to analyze.
Each game is described by six lines:
- — the number of rows of the board
- — the number of columns of the board
- — the starting row of the pawn
- — the starting column of the pawn
- — the starting row of the knight
- — the starting column of the knight
Row is the bottom row and row is the top row; column is the leftmost column and column is the rightmost. The pawn and the knight always start on different squares.
Output
For each game, print exactly one line:
Win in K knight move(s).if the knight can win, where is the minimum number of knight moves.Stalemate in K knight move(s).if the knight cannot win but can force a stalemate, where is the minimum number of knight moves.Loss in K knight move(s).otherwise, where is the number of moves the knight makes before the pawn reaches the top row.