TopCoder problem "HigherMaze" used in TCI '02 Semifinals 1 (Division I Level Three)

Problem Statement

We all know that there are not necessarily three dimensions, and that there are wormholes scattered throughout the universe which will transport you through time and space. However, because it is often difficult for people to conceptualize higher dimensions, we will probably have to have computers do most of our navigation for us. Your task is to write a program that will simulate a pseudo-random asteroid field, and then navigate a ship through the asteroid field as quickly as possible.

The first step will be to generate the asteroid field. You will be given a int[], dim, that will specify how large you should make each dimension in your asteroid field. For example, if dim is {3,4,5}, the generated asteroid field will be a 3 x 4 x 5 box, with corners at (0,0,0) and (2,3,4). If dim is {3,4,5,4}, the generated asteroid field will be a 3 x 4 x 5 x 4 hyper-box (a hyper box is analogous to a regular box, but in more than three dimensions). Then, you must determine which spaces in the asteroid field actually contain asteroids. This will be done pseudo-randomly using something like the following code, where a and p are inputs (remember that there are a variable number of dimensions):

int current = 1;
for(int i₀ = 0; i₀<dim₀; i₀++)
for(int i₁ = 0; i₁<dim₁; i₁++)
... one loop per dimension
{
    current = (current*a)%p;
    if((current&1)==1){
        //add an asteroid at (i₀,i₁,i₂,...)
    }
}

Once the asteroid field is generated, you have to navigate through it. You will be given a int[], start, and a int[], finish. You must find your way through the asteroid field, as quickly as possible without running into an asteroid. You may move from any location (a₀,a₁,a₂...) to any other location, (b₀,b₁,b₂...) so long as for all i, the differences between a_i and b_i is either 1 or 0, and b_i is between 0 and dim_i-1, inclusive. Each such movement takes one unit of time. For example, if you were at the S below, you could move to any of the locations marked with T, where '.' represents open space.

.....
.TTT.
.TST.
.TTT.
.....

In addition to this type of movement, you may also (but are not required to) travel through wormholes. You will be given a String[], wormholes, which specifies the origin, length of time travel, and destination of some wormholes. To go through a wormhole, you must first reach the origin of the wormhole. Then, after going through the wormhole, you will be transported to the destination of the wormhole. Additionally, wormholes transport you in time. So, each wormhole has a fixed amount of time travel associated with it, and each time you go through the wormhole, you will go forward or backward in time by that amount. Each element of wormholes will be formatted as "<origin> <time> <destination>", where <origin> and <destination> and coordinates as a space delimited list. For example, "0 0 -1 3 7" would represent a wormhole that starts at (0,0), transports you back in time 1 unit, and leaves you at (3,7) in space. Thus, if you reached (0,0) 5 units of time after you started, it would be possible to reach (3,7) from there 4 units of time after you started.

Sometimes, it will be impossible to reach finish from start. In this case return, 2^31-1 = 2147483647.

Definition

Class:	HigherMaze
Method:	navigate
Parameters:	int, int, int[], int[], int[], String[]
Returns:	int
Method signature:	int navigate(int a, int p, int[] dim, int[] start, int[] finish, String[] wormholes)
(be sure your method is public)

Constraints

The product of all the elements of dim will be between 2 and 1000, inclusive.

Each element of dim will be between 2 and 20, inclusive.

dim will contain between 1 and 5 elements, inclusive.

a and p will be between 1 and 2,000,000,000, inclusive.

a times p will be between 1 and 2,000,000,000, inclusive.

start and finish will be within the hyper-box defined by dim.

start and finish will be both be empty space (not an asteroid, possibly a wormhole).

wormholes will contain between 0 and 50 elements, inclusive.

Each element of wormholes will be formatted as "<origin> <time> <destination>".

<origin> and <destination> will both be space delimited (no extra, leading or trailing spaces) lists of integers, representing a coordinate in space within the hyper-box defined by dim.

<origin> and <destination> will both be empty space (not an asteroid).

<time> will be an integer in the range -1,000,000 to 1,000,000.

There will be no way to go back in time infinitely. (In other words, there will be no reachable cycles that take negative amounts of time. However, there may be unreachable ones, but they can not affect the return, since they are unreachable.)

Examples

{5,5}

{0,0}

{4,4}

{}

Returns: 6

This input generates the following two dimensional asteroid field, where an 'X' is an asteroid, and a '.' is open space. (Here, (0,0) is the upper left corner, and (4,4) is the lower right, and (4,0) is in the lower left):

...XX
XX.X.
..XXX
....X
.XXX.

Here is one path that takes 6 time units, where 'S' represents the start, 'F' the finish, and '*' the path.

S*.XX
XX*X.
.*XXX
..**X
.XXXF

{5,5}

{0,0}

{4,4}

{"0 0 2 4 4"}

Returns: 2

While there is still a path from (0,0) to (4,4) which takes 6 time units, there is also a wormhole, which transports you directly from (0,0) to (4,4), and ahead 2 units of time.

{5,5}

{0,0}

{4,4}

{"0 0 2 4 4","0 0 8 1 4","0 2 5 1 4","1 4 -8 4 4"}

Returns: -1

This is the same asteroid configuration as the previous two examples, but now there are more wormholes. The quickest way to get from (0,0) to (4,4) is to move from from (0,0) to (0,2), which takes 2 units of time. From (0,2) we should go through the wormhole to (1,4), which transports us ahead 5 units of time, for a total of 7. Then, we can take the wormhole from (1,4) to (4,4), which takes us back 8 units of time. Thus, the total time for the trip is 2 + 5 - 8 = -1, and we arrive before we left!

(note that two wormholes can start at the same location, and could even start and end at the same location)

{20,20}

{1,2}

{12,12}

{}

Returns: 23

{20,20}

{0,2}

{18,19}

{"0 2 -100000 0 19","4 18 -100000 7 0","8 0 1000000 19 10","19 6 -800000 13 8"}

Returns: 21

The only way to get all the way is to go through all 4 wormholes, in order.

{5,5}

{0,0}

{4,0}

{"0 0 -6 4 4"}

Returns: -2

{20}

{2}

{19}

{}

Returns: 2147483647

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1131

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4370&pm=1131

Writer:

lars2520

Testers:

alexcchan , lbackstrom , brett1479

Problem categories:

Graph Theory