Problem Statement |
| | Given a starting point and a finishing point on a square grid, along with some
grid points that are forbidden, determine the length of the shortest path
from start to finish. In one step you may move one unit horizontally,
vertically, or diagonally (but not onto a forbidden point).
Create a class ShortPath with a method steps that is given int[] x and int[] y as input. Corresponding elements of x and y give the coordinates of a point. The first elements of
x and y give the start, the second elements give the finish, and additional corresponding
pairs of elements from x and y specify forbidden points. Your method should return the minimum
number of steps required to go from start to finish, or -1 if it is not possible to go from start
to finish.
|
| |
Definition |
| | | Class: | ShortPath | | Method: | steps | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int steps(int[] x, int[] y) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | x will have between 2 and 50 elements inclusive. |
| - | y will have the same number of elements as x. |
| - | Each element of x will be between -1,000,000,000 and 1,000,000,000 inclusive. |
| - | Each element of y will be between -1,000,000,000 and 1,000,000,000 inclusive. |
| - | The start and finish points will be distinct from each other and from all other points given by x and y. |
| |
Examples |
| 0) | |
| | | Returns: 3 |
3 --|--|--|--|--|--|--
2 --|--|--F--|--|--|--
1 --|--X--|--|--|--|--
0 --S--|--|--|--|--|--
0 1 2 3 4 5
In the diagram, S is the start point, F is the finish, and X is forbidden.
There are two different paths of length 3, one of which is S to (0,1) to (1,2) to F.
The direct path of length 2 is blocked by the forbidden point.
|
|
|
| 1) | |
| | | Returns: 1 | |
Take a single diagonal step from (0,0) to (1,1). The second appearance of (2,2) on the forbidden list is legal but never matters. |
|
|
| 2) | |
| | {1,100000,0,0,0,2,2,2,1,1} | {1,200000,0,1,2,0,1,2,0,2} |
| Returns: -1 | | The start point is trapped in a square of forbidden points. |
|
|
| 3) | |
| | {1,100000,0,0,0,2,2,2,1} | {1,200000,0,1,2,0,1,2,0} |
| Returns: 199999 | |
|