Problem H
Avoiding Jungle in the Dark
Input: Standard Input
Output: Standard
Output
A Pilgrim is all set for a long
journey to the
Given the map of the route, help the Pilgrim to determine the minimum time that would be required to travel from the starting position to the destination.
The first line of input contains a positive integer T<=100. Each of the next T lines contains a string of length at least 2 and at most 1000. The string will always begin with an S and end with a D. The characters in between will be either a ‘.’ Or ‘*’, quotes for clarity. Here a ‘.’ represents a plain land and ‘*’ a jungle. It takes exactly one hour to travel from one position to the next and the Pilgrim never travels backward. Note that he is always located at the left most position of a particular land and when he travels to the next land, he travels for a full hour to the reach the left most position of the next land.
For each case of input there will be one line of output. It will first contain the case number followed by the minimum time required to reach the destination. In case it is not possible to reach the destination, output -1. Note that he starts his journey from the position marked S and finishes at D. On the first day of his journey, he is located on S at 6 AM. Dark hours are considered to be the time between 6 PM to 6 AM inclusive.
3 S.......D S...****................***.D S***********.***********D |
Case #1: 8 Case #2: 36 Case #3: -1 |
Problemsetter: Shamim Hafiz
Special
Thanks to: