ShortPath | Topcoder Archive

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,2,1}
```
```
{0,2,1}
```
```
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.
```
{0,1,2,2}
```
```
{0,1,2,2}
```
```
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.

{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.

{1,100000,0,0,0,2,2,2,1}

{1,200000,0,1,2,0,1,2,0}

Returns: 199999

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.