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)

It says that their positions will be inputted as "X Y" - however, it's more like "Y X", since the first number is the row and the second is the column.

I assume he can't jump diagonally?

He can jump anywhere, in any way as long as it's within his distance range. (distance here means sqrt(dx^2+dy^2) )