PROBLEM STATEMENT
When traveling in a canal one can travel horizontally or downward, however, by
a system of locks, a vessel can also be elevated. Given a description of a
(possibly unrealistic) canal, calculate the shortest time it will take a vessel
to get from the start coordinate to the end coordinate, following these rules:
*When traveling level or downwards, the vessel travels at a constant time per
coordinate (defined as 1 time unit).
*When traveling upwards, the vessel must spend an extra second traveling the
lock for each level in addition to the natural movement time in the first rule
(i.e. from 8 to 9 takes 2 seconds, from 5 to 8 takes 4 seconds).
*If the decline is steeper than 2 (i.e. from 5 to 2) then the vessel cannot
travel it safely, and will not attempt to do so. Note that it CAN GO UP
steeper than 2, but takes more time (as above).
You will be given a String[] that will represent the height of the canal at
each coordinate. The first element of the String[] will be the top row, and
the last element will be the bottom row. A blank coordinate indicates that the
canal is non-existant at that location.
You will also be given two additional Strings, one for the start coordinate and
one for the end coordinate. Both are formatted as:
"X Y"
(quotes added for clarity) with exactly one space in between the two integers.
These coordinates will be 0-based (top left is "0 0").
A vessel can only travel the four compass directions (North, South, East,
West), and not diagonally (from "1 1" to "0 0" takes 2 time on a level,
connected canal).
Implement a class Canals containing a method bestTime(). bestTime should
return an int representing the least amount of time needed to get from the
start coordinate to the end coordinate. If the vessel can not get from the
start coordinate to the end coordinate, bestTime should return -1.
DEFINITION
Class name: Canals
Method name: bestTime
Parameters: String[], String, String
Returns: int
The method signature is:
int bestTime(String[] canal, String start, String end)
Be sure your method is public.
TopCoder will ensure the following:
*canal contains between 2 and 20 elements, inclusive.
*each element of canal will contain between 2 and 20 characters, inclusive, and
they will all contain the same number of characters.
*each character of each element of canal will be a digit [0-9] or a space.
*start and end will be correctly formatted Strings: "X Y" (with one space).
*start and end will both be a coordinate in which the canal exists.
*start and end will not be the same coordinate.
EXAMPLES
(quotes added for clarity)
canal=
{"123",
"2 2",
"313"}
start = "2 2"
end = "0 0"
By starting going "north", the vessel will take 1 + (1 + 1) + 1 + 1 = 5 time.
The parenthesis represent the calculation for the lock.
canal=
{"12345",
"2 4 6",
"34567",
"4 6 8",
"56789"}
start = "4 4"
end = "0 0"
All paths have the same time, and that time is 8.
canal=
{"12345",
"2 4 6",
"34567",
"4 6 8",
"56789"}
start = "0 0"
end = "4 4"
In addition to the 8 time it takes to travel the distance, 8 locks had to be
climbed. The return value is 16.
canal=
{"798",
"788",
"899"}
start = "2 0"
end = "0 0"
Although it means going up a lock, going straight "west" results in a return of
3.
canal=
{"698",
"788",
"899"}
start = "2 0"
end = "0 0"
This situation has changed because the vessel cannot go from 9 to 6. Therefore
the shortest time is 4.
canal=
{"111 ",
"1 1 1 ",
"111 "}
start = "2 2"
end = "4 1"
Notice that the target is an unreachable 1x1 canal segment. This is a legal
setup, and the return is -1.