Problem Statement |
| | The game of Errant Knights is played on an infinite chessboard using two knights, white and black. The players alternate turns and the white player starts the game. Each player makes a normal chess knight's move with his knight, but there is a restriction that each move must make the Euclidean distance between the two knights smaller. A player can make more than one move in a single turn, but then each move must go in the same direction.
For example, if the black knight is at coordinates (0, 0) and the white knight is at (9, 5), then the white knight can move to (7, 4), (5, 3), (3, 2), (1, 1), (-1, 0). Further moving in this direction is not allowed because (-3, -1) is further from (0, 0) than (-1, 0). Of course, the white knight could also start his turn by moving in one of several other directions, and then possibly making more moves in that direction.
The game ends when one of the knights wins by capturing the other one (by moving to its position), or when it is impossible to make another move (because the knights are orthogonally next to each other and each move would increase the distance). In the second case, the player who should make the next move loses.
Several games of Errant Knight will be played. The starting position of the white knight in the i-th game is (x[i], y[i]). The black knight will start each game at (0, 0). Both players play optimally. Return a String where the i-th character is 'B' if the black knight wins the i-th game or 'W' if the white knight wins.
|
| |
Definition |
| | | Class: | ErrantKnight | | Method: | whoWins | | Parameters: | int[], int[] | | Returns: | String | | Method signature: | String whoWins(int[] x, int[] y) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A chess knight can move in 8 directions. From (0, 0), a knight could move to (2, 1), (2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2), (-2, 1), (-2, -1). |
| |
Constraints |
| - | x and y will contain between 1 and 50 elements, inclusive. |
| - | x and y will contain the same number of elements. |
| - | Each element of x will be between -4000 and 4000, inclusive. |
| - | Each element of y will be between -4000 and 4000, inclusive. |
| - | For each i, x[i] and y[i] cannot both be equal to 0. |
| |
Examples |
| 0) | |
| | {1,1,2,2,9,3} | {0,1,0,1,5,3} |
| Returns: "BWWWWB" | In the first game, there is no possible move for White from (1,0), so Black wins.
In the second game, White moves from (1,1) to (0,-1). Black has no legal move from there, so White wins.
In the third game, White moves from (2,0) to (0,1). Again, Black has no legal move, and White wins.
In the fourth game, White moves from (2,1) to (0,0), and captures the Black knight. White wins.
In the fifth game, White makes five moves from the same direction, moving from (9,5) to (-1,0). White wins.
In the sixth game, White can make a sequence of moves which lead to one of the following squares: (2,1), (1,-1), (1,2), (-1,1), (4,1), (1,4). After each of these moves Black can win.
|
|
|
| 1) | |
| | {1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,7} | {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7} |
| Returns: "BWBBBBBWWWWWWWWWWWWWWWWBWWWWWWWBWWWWWWWBWWWWWWWWWB" | |
|
| 2) | |
| | | Returns: "B" | | Note that x[i] and y[i] can be negative.
|
|
|