Woburn Challenge 1998
Like we said earlier, Luke Skywalker is a wimp and so Yoda is having a really hard time turning him into a worthy Jedi Knight. His first lesson is in the Bogs of Endor, a large swamp that has several solid surfaces in various places. Luke can only stand on one of the solid surfaces, otherwise he will sink into the swamp and be eaten by a really disgusting looking creature (and Yoda won't be too pleased with that). His training exercise consists of the following. Yoda will place him on one of the solid surfaces to start. He must then use the power of the Force to jump between solid surfaces till he reaches Yoda, who is on another solid surface some distance away. Luke is still a Young Jedi, so his jumping range is limited. Yoda is an impatient "man" and so Luke must find the quickest way to get to Yoda.
Input Specification
You will be given a *
(representing a solid surface) or the letter o
representing no solid
surface. You will also be told of Luke's starting point and Yoda's
position. You will also be given the maximum distance that Luke can
jump.
All inputs will be integers in the range
Line 1:
Line 2:
Line 3: Luke's maximum jumping distance
The next
The next line will contain Luke's starting position as
The next line will contain Yoda's position as
You will then be given more pairs of lines giving new positions for Luke
and Yoda. The input will be terminated by a single line containing
-1 -1
(i.e. starting coordinates are
Output Specification
You will output the smallest number of jumps that Luke needs to make to
reach Yoda from where he is for each starting position (each one on a
separate line). If he cannot reach Yoda, then output THERE IS NO TRY
.
Sample Input
5
5
2
oooo*
ooo*o
oo*o*
ooo**
*ooo*
5 1
1 5
5 5
1 5
-1 -1
Sample Output
THERE IS NO TRY
2
Comments
This problem uses the Euclidean distance.