PROBLEM STATEMENT:
A bullfrog sitting on one side of a stream would like to get to the other side
of that stream using as few jumps as possible. The stream has parallel sides,
and its width will be provided as a parameter. The stream extends infinitely
in both the up and down directions. In the diagram below, of a small section of
the stream, the lower left corner of the stream is at point (0,0). The lower
right corner (if you orient the stream so that it's vertical as shown below),
is (width, 0):
| |
land | stream | land
| |
(0,0) -> | | <-- (width, 0)
All coordinates used in this problem will be given in (x, y) form, where x is
the horizontal axis and y is the vertical axis (using the figure shown above).
The frog will always start out on the left side of the stream.
The stream may contain a number of lilypads, which the frog can use as jumping
platforms. Lilypads will always be perfect circles. The center coordinate and
radius of each lilypad will be provided in the arguments. Lilypads do not have
to exist entirely on the water - they can exist entirely or partially on the
land as well (in the case of a lilypad existing only partially on the land, the
rest of it will lie on the water - see example 3).
The bullfrog has a maximum jumping range - it can jump no farther than its
maximum range, but it can make any jump that is shorter than or equal to its
maximum range. Jumping range is measured as the distance between the frog's
takeoff point and its landing point. This particular bullfrog is very
talented, and can jump from the extreme outer edge of a surface and land on the
extreme outer edge of another surface without falling into the water (see
example 3).
Aside from the water, the frog is able to walk around on any surface - it can
walk from one surface to another without jumping at all if it can find a
gapless route. Even if two surfaces only meet at a single point, the frog can
cross between them without jumping (see example 2).
Implement a class Bullfrog, which contains a method minJumps. This method will
return an int representing the minimum number of jumps required for the frog to
cross the stream. If there is no way for the frog to cross the stream, return
-1.
The method will be passed three parameters:
* String[] lilypads - Each string will represent a lilypad, and will be in the
form "x y r" (not including the quotes), where x is the x-coordinate, y is the
y-coordinate, and r is the radius of the lilypad.
* int width - The width of the stream.
* int maxJump - The maximum jumping range of the bullfrog.
TopCoder will ensure the validity of the inputs. Inputs are valid if
all of the following criteria are met:
* lilypads will contain between 0 and 50 elements inclusive.
* Each string in lilypads will be of the form "x y r" (not including the
quotes). x will be between -5000 and 5000 inclusive. y will be between -5000
and 5000 inclusive. r will be between 1 and 5000 inclusive. There will be
exactly one space separating each value, and there will be no other spaces in
the string.
* width will be between 1 and 4500 inclusive.
* maxJump will be between 0 and 1000 inclusive.
NOTES
* The frog may not enter the water at any point during its journey across the
stream.
DEFINITION
Class name: Bullfrog
Method name: minJumps
Parameters: String[], int, int
Returns: int
The method signature is:
public int minJumps(String[] lilypads, int width, int maxJump);
Make sure your method is public.
EXAMPLES
(see http://www.topcoder.com/contest/frog.html for illustrations)
---------
Example 1
---------
lilypads: {"5 5 1", "3 3 1", "8 7 1"}
width: 10
maxJump: 5
return value: 2
The frog can jump from the left edge to the lilypad at (5,5). It can then jump
to the right edge of the stream, for a total of 2 jumps.
---------
Example 2
---------
lilypads: {"3 3 2", "7 3 2"}
width: 10
maxJump: 4
return value: 2
The frog can jump from the left edge to the lilypad at (3,3). It can then walk
to the other lilypad because the two lilypads touch each other (only at one
point, but that's enough for the frog to cross lilypads without jumping). The
frog can then jump to the right edge of the stream, for a total of 2 jumps.
---------
Example 3
---------
lilypads: {"3 6 2", "4 3 2", "15 3 3"}
width: 15
maxJump: 6
return value: 2
The frog can jump to either the lilypad at (3,6) or the lilypad at (4,3). If
it jumps to the lilypad at (3,6), it can walk to the one at (4,3) because the
lilypads overlap. The frog can then jump from the very edge of the lilypad at
(4,3) to the edge of the lilypad at (15,3) - from point (6,3) to point (12,3).
It can then walk to the right edge of the stream, for a total of just 2 jumps.
---------
Example 4
---------
lilypads: {}
width: 10
maxJump: 9
return value: -1
The frog cannot make it across the stream - it is wider than he can jump, and
there are no lilypads to assist.