Problem Statement |
| | You have an infinite chessboard with several black pieces placed on it. You have a white knight on the same chessboard, which starts from the (0, 0) point, and you want to know how fast it can capture all the black pieces.
You will be given a String[] pieces, containing information about black pieces. Each element of pieces will be formatted as "X Y", where X and Y are integer numbers between -1000000 and 1000000, inclusive. Your method should return the minimum number of moves needed to capture all the black pieces, assuming none of them move. |
| |
Definition |
| | | Class: | GetThemAll | | Method: | quickKnight | | Parameters: | String[] | | Returns: | int | | Method signature: | int quickKnight(String[] pieces) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if a knight is at (0,0), it may move to (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2). |
| - | The knight starts at (0, 0). |
| |
Constraints |
| - | pieces will contain between 0 and 9 elements, inclusive. |
| - | Each element of pieces will be formatted as "X Y", where X and Y are integer numbers without extra leading zeroes. |
| - | X and Y will be between -1000000 and 1000000, inclusive, in each element of pieces. |
| - | All elements of pieces will be different. |
| - | There are no pieces at (0, 0). |
| |
Examples |
| 0) | |
| | |
| 1) | |
| | {"2 -1", "2 1", "-2 1", "-2 -1"} |
| Returns: 7 | | The knight should return to the starting position several times. |
|
|
| 2) | |
| | | Returns: 3 | | The knight needs 3 jumps to move to any adjacent cell. |
|
|
| 3) | |
| | |
| 4) | |
| | {"-1000000 -1000000", "1000000 1000000", "1000000 -1000000", "-1000000 1000000"} |
| Returns: 3666668 | | One really big square, containing the maximal possible distance between two pieces. |
|
|