TheEasyChase
SRM 423 · 2008-10-28 · by Vasyl[alphacom]
Problem Statement
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).
Constraints
- n will be between 2 and 20, inclusive.
- rowWhite will be between 1 and n, inclusive.
- colWhite will be between 1 and n, inclusive.
- rowBlack will be between 1 and n, inclusive.
- colBlack will be between 1 and n, inclusive.
- (rowWhite, colWhite) and (rowBlack, colBlack) will represent different cells.
2 1 1 2 2 Returns: "BLACK 2"
There are two possible moves for the first player. But he will lose the game anyway.
2 2 2 1 2 Returns: "WHITE 1"
Just one move in this game.
3 1 1 3 3 Returns: "BLACK 6"
3 3 2 1 1 Returns: "BLACK 8"
3 1 2 3 1 Returns: "BLACK 8"
Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheEasyChase with a public method string winner(int n, int rowWhite, int colWhite, int rowBlack, int colBlack) · 85 test cases · 2 s / 256 MB per case