PROBLEM STATEMENT
You are almost home when a storm pops up out of nowhere and you are caught
without an umbrella. You are wearing your best suit (or best T-shirt, as the
case may be) and want to stay as dry as possible. Through a sudden bout of
prescience, you are aware of where every raindrop will fall. You rush for
cover and whip out your trusty laptop and code up an algorithm that will tell
you the best way to go to remain dry, given your knowledge of when and where
the raindrops will fall.
Starting from position 0 at time 0 and ending at position endPos at time less
than or equal to the size of the raindrops parameter, you must find the dryest
path home. Your path will be in a straight line and at each time period you
will have three choices: you may either move forward one position, backward one
position, or remain where you are. However, you can not move backwards beyond
position 0. i.e. negative positions are not allowed.
You will be given a set of strings which tell you where raindrops will fall at
each time period. Thus, the string at index 0 will tell you where raindrops
will fall at time = 0, before you have made your first move (or stayed still,
as the case may be). Each string will contain a series of numbers separated by
one or more spaces, representing the positions of the raindrops at the given
time. Thus if the string at index 0 is "0 2 5" one raindrop will fall at
positions 0, 2, and 5.
DEFINITION
Class: Raindrops
Method: dryestPath
Parameters: String[], int
Returns: int
Method signature (be sure your method is public): int dryestPath(String[]
raindrops, int endPos);
NOTES
- Strings may contain repeated numbers. These indicate more than 1 raindrop
falls at the corresponding position at the corresponding time.
- raindrops will fall at time 0 before you have a chance to move (see example 2).
- the dryest path must end at time less than or equal to the size of the
raindrops parameter (see example 1).
- if no raindrops fall at some time, this will be represented by a string
composed entirely of spaces.
- elements of raindrops may contain leading or trailing spaces.
- leading 0's and extra spaces are allowed.
- backwards moves into negative positions are not allowed.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- raindrops will contain between 1 and 50 elements, inclusive.
- each element of raindrops will contain between 1 and 50 characters, inclusive.
- each character of raindrops will be either a digit or a space.
- each raindrop position will be at least 0 and less than endPos.
- endPos will be greater than 0 and less than or equal to the number of
elements in raindrops.
EXAMPLES
In describing paths, we will use the shorthand F = forward, B = back, and S =
stay in place.
Thus FFB would mean forward twice and then backwards once.
This has nothing to do with return values, it is only a shorthand being used in
the examples to convey a path.
1. raindrops = {" ","1","1"}, endPos = 3
We must reach position 3 by time 3 (see NOTES).
Since endPos = 3 and the maximum time is 3, there is only one possible path to
the position endPos within the time limit, which is to go forward 3 times (FFF).
At time 0, no raindrops fall and then we move forward to position 1.
At time 1, a raindrop falls at position 1 and hits us. Then we move forward to
position 2.
At time 2, a raindrop falls at position 1 but does not hit us. Then we move
forward to position 3.
At time 3 we are home.
Since we were only hit by one raindrop at time 1, the method returns 1.
2. raindrops = {"0 2","1","2","0 1"}, endPos = 3
In this case the shortest path is: SFFF
At time 0, two raindrops fall, one of them at position 0, hitting us. We stay
at position 0
At time 1, a raindrop falls at position 1 but we are at position 0. Then we
move forward to position 1.
At time 2, a raindrop falls at position 2 but does not hit us at position 1.
Then we move forward to position 2.
At time 3, a raindrop falls at positions 0 and 1 but does not hit us at
position 2. Then we move forward to position 3.
At time 4 we are home.
Since we were only hit by one raindrop, at time 0, the method returns 1.
3. raindrops = {"2","1 3","0 2","1 2 3","2 3","3","0 1 2","3"}, endPos = 4
returns 0
4. raindrops = {"2 0","1 1 3","0 4 2","1 2 2 0 3","1 2 3 4","5 4 2 2 0","0 2 1
5"," "}, endPos = 6
returns 3