Connection Status:
Competition Arena > ShortPath

ShortPath

TCCC '04 Semifinals 3 · 2004-02-23 · by dgoodman

TCCC '04 Semifinals 3 · 2004-02-23 · by dgoodman · Graph Theory
Class Name: ShortPath
Return Type: int
Method Name: steps
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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

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

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
4)
{-1000000000,1000000000,-1,0,1,2}
{-1000000000,1000000000,0,0,0,0}
Returns: 2000000002

Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ShortPath with a public method int steps(vector<int> x, vector<int> y) · 38 test cases · 2 s / 256 MB per case

Submitting as anonymous