A Knightly Pursuit

Time limit1sMemory limit128 MB

Summary
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 8×88 \times 8 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 22 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 KK and the squares it can move to are marked 11 to 88:

. . . . . . .
. . 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 nn, the number of games to analyze.

Each game is described by six lines:

  • rr — the number of rows of the board (3≤r<100)(3 \le r < 100)
  • cc — the number of columns of the board (2≤c<100)(2 \le c < 100)
  • prpr — the starting row of the pawn (1≤pr≤r)(1 \le pr \le r)
  • pcpc — the starting column of the pawn (1≤pc≤c)(1 \le pc \le c)
  • krkr — the starting row of the knight (1≤kr≤r)(1 \le kr \le r)
  • kckc — the starting column of the knight (1≤kc≤c)(1 \le kc \le c)

Row 11 is the bottom row and row rr is the top row; column 11 is the leftmost column and column cc 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 KK is the minimum number of knight moves.
  • Stalemate in K knight move(s). if the knight cannot win but can force a stalemate, where KK is the minimum number of knight moves.
  • Loss in K knight move(s). otherwise, where KK is the number of moves the knight makes before the pawn reaches the top row.

Examples1

  1. Example 1

    Input
    3
    99
    99
    33
    33
    33
    35
    3
    3
    1
    1
    2
    3
    99
    99
    96
    23
    99
    1
    
    Expected output
    Win in 1 knight move(s).
    Stalemate in 1 knight move(s).
    Loss in 2 knight move(s).