Woburn Challenge 1998
Episode 3: "Do or Do Not, There is no Try"
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
You will be given a k x n grid (total grid size ≤ 32000) representing the swamp. Each point in the grid will be marked either "*" (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 1 ≤ number ≤ 32000.
Line 1: k
Line 2: n
Line 3: Luke's maximum jumping distance
The next k lines will contain the grid (n characters on each line). Note that
the topleft corner of the grid is at coordinate (1,1)
The next line will contain Luke's starting position as x0 y0 (separated by one
space).
The next line will contain Yoda's position as x1 y1 (separated by one space).
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" (ie.
starting coordinates are -1, -1).
Output
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
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)