Two players play a simple game on a n x n board. The first player has a single white checker which is initially located at (rowWhite, colWhite). The second player has a single black checker which is initially located at (rowBlack, colBlack). All coordinates are 1-based. The two players alternate turns, and the first player moves first.
When it is the first player's turn, he chooses one of four directions (up, down, left or right) and moves his checker one cell in the chosen direction. When it is the second player's turn, he also chooses one of those four directions and moves his checker one or two cells in the chosen direction. A player wins the game when his move puts his checker in the cell occupied by his opponent's checker.
Both players use an optimal game strategy. If the player can win, he will follow the strategy that minimizes the number of moves in the game. If the player cannot win, he will follow the strategy that maximizes the number of moves in the game.
If the first player will win, return "WHITE x", and if the second player will win, return "BLACK x", where x is the number of moves in the game (all quotes for clarity).
|