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).
Definition
- Class:
- TheEasyChase
- Method:
- winner
- Parameters:
- int, int, int, int, int
- Returns:
- String
- Method signature:
- String winner(int n, int rowWhite, int colWhite, int rowBlack, int colBlack)
- (be sure your method is public)
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.
Examples
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"
3
2
2
3
1
Returns: "BLACK 6"
8
5
4
1
1
Returns: "BLACK 22"
8
5
1
7
3
Returns: "BLACK 14"
8
6
4
6
5
Returns: "WHITE 1"
4
3
2
1
3
Returns: "BLACK 8"
16
9
13
5
1
Returns: "BLACK 42"
15
13
12
6
13
Returns: "BLACK 36"
15
7
5
7
11
Returns: "BLACK 30"
12
7
1
6
7
Returns: "BLACK 20"
16
3
9
12
5
Returns: "BLACK 36"
15
10
4
4
8
Returns: "BLACK 30"
14
1
7
3
1
Returns: "BLACK 28"
11
5
4
9
4
Returns: "BLACK 24"
18
1
1
9
9
Returns: "BLACK 30"
10
9
7
7
10
Returns: "BLACK 20"
17
2
2
1
1
Returns: "BLACK 34"
15
2
2
1
1
Returns: "BLACK 30"
19
2
2
1
1
Returns: "BLACK 38"
20
19
2
20
1
Returns: "BLACK 40"
20
1
20
20
1
Returns: "BLACK 56"
19
1
19
19
1
Returns: "BLACK 54"
20
1
1
19
20
Returns: "BLACK 56"
20
11
11
1
1
Returns: "BLACK 58"
20
20
19
1
1
Returns: "BLACK 58"
20
1
17
5
9
Returns: "BLACK 46"
20
8
12
11
13
Returns: "BLACK 42"
20
7
5
17
11
Returns: "BLACK 46"
20
19
9
14
11
Returns: "BLACK 28"
20
1
2
1
20
Returns: "BLACK 58"
19
1
2
19
19
Returns: "BLACK 56"
18
1
1
1
18
Returns: "BLACK 52"
20
1
1
10
10
Returns: "BLACK 34"
20
1
1
20
20
Returns: "BLACK 56"
20
7
14
19
2
Returns: "BLACK 54"
5
5
5
4
4
Returns: "BLACK 2"
20
1
1
20
19
Returns: "BLACK 56"
19
1
1
17
18
Returns: "BLACK 50"
20
1
2
20
18
Returns: "BLACK 54"
19
2
9
19
1
Returns: "BLACK 56"
20
5
7
17
19
Returns: "BLACK 54"
19
1
3
17
17
Returns: "BLACK 50"
20
2
2
4
3
Returns: "BLACK 40"
20
1
20
1
2
Returns: "BLACK 56"
20
10
10
10
12
Returns: "BLACK 40"
20
2
5
11
17
Returns: "BLACK 44"
19
2
5
5
7
Returns: "BLACK 36"
20
2
3
20
20
Returns: "BLACK 58"
20
18
19
2
1
Returns: "BLACK 56"
5
2
1
5
3
Returns: "BLACK 8"
10
1
1
3
2
Returns: "BLACK 20"
6
6
3
2
2
Returns: "BLACK 12"
20
1
1
19
17
Returns: "BLACK 54"
20
1
1
10
20
Returns: "BLACK 48"
20
4
7
18
17
Returns: "BLACK 52"
20
1
1
2
3
Returns: "BLACK 40"
20
5
6
3
4
Returns: "BLACK 46"
19
3
4
19
18
Returns: "BLACK 52"
20
1
1
2
4
Returns: "BLACK 40"
20
2
2
1
1
Returns: "BLACK 40"
6
1
1
5
6
Returns: "BLACK 14"
20
19
20
1
1
Returns: "BLACK 58"
20
1
1
10
19
Returns: "BLACK 48"
20
1
1
17
19
Returns: "BLACK 54"
3
1
1
3
2
Returns: "BLACK 6"
20
1
1
1
4
Returns: "BLACK 40"
20
20
20
17
18
Returns: "BLACK 40"
19
1
8
10
17
Returns: "BLACK 40"
20
2
20
20
19
Returns: "BLACK 54"
20
1
1
3
2
Returns: "BLACK 40"
20
2
6
11
19
Returns: "BLACK 46"
20
2
3
18
17
Returns: "BLACK 52"
20
1
1
19
18
Returns: "BLACK 54"
20
4
15
4
5
Returns: "BLACK 48"
20
17
3
1
8
Returns: "BLACK 50"
20
1
1
3
3
Returns: "BLACK 6"
20
20
20
20
19
Returns: "WHITE 1"
9
4
4
6
4
Returns: "BLACK 18"
20
2
3
13
19
Returns: "BLACK 48"
20
2
3
19
20
Returns: "BLACK 56"
3
1
1
2
3
Returns: "BLACK 6"