Swing Through Trees with Your Grappling Hook

Question

You have found the path through the forest and now plan on travelling along it. However, just before you start on your journey, the ground turns into lava.

You manage to scurry up the nearest tree (the trees have inexplicably not burnt up), but now you are faced with a problem: how can you get out of the forest when the floor is lava? The answer hits you like a good idea for a programming challenge - you can use your magical grappling hook (made from a piece of the canoe earlier) to swing through the trees and the branches!

However, you're not sure which trees and branches you need to swing on to get there. Luckily, you have your programming skills, so you decide to draw a program on your arm to tell you which trees to swing on. However, there is not much surface area on your arm, so you must make the program as small as possible.

We can represent a forest using a n by m array. The following characters will make up the array:

• T: A tree. You can land here. You cannot use your grappling hook on this. You can swing through this.
• P: Functions the same as T. You start here.
• Q: Functions the same as T. This is the goal.
• +: A branch. You cannot land here. You can use your grappling hook on this. You can swing through this.
• *: A man-eating spider. If you land here, you die. If you use your grappling hook on this, you die. If you swing through this, you die.
• -: Regular ground, in other words, lava. You cannot land here. You cannot use your grappling hook on this. You can swing through this. All area outside of the given array is this type.

Here is an example of what a forest might look like:

               y
----T---+------12
---------------11
----T---+---T--10
---------------9
T-+-T-+-T------8
---------------7
------------+--6
----+----------5
+-------+------4
---------------3
----P---+-*-Q--2
---------------1
T-+-T-+-T------0
012345678911111
x         01234

I will refer to coordinates with the notation (x,y), as shown on the axes.

You begin from P and have to make your way to Q. To do this, you swing from tree T to tree T using branches +. You can attach your grappling hook on any branch that is orthogonal to you - that is, a branch that is either on the same x position or y position that you are in. For instance, if you were at the position (4,8) in the example forest, you could attach your grappling hook to the positions (2,8), (6,8), or (4,5). You can attach this even if there are trees or other branches between you and the branch.

Once you attach your grappling hook onto a branch, you will travel a distance in the direction of the branch equal to twice the distance between your initial position and the branch. In other words, your final position will be the same distance from the branch as your starting position, just on the opposite side. A more formal definition of how the movement works is below. A subscript of v is the final position, u is the initial position, and b is the position of the branch.

$$(x_v, y_v) = (2x_b-x_u, 2y_b-y_u)$$

Note that if there is a spider between your initial position and your final position, you cannot go there. For example, in the example forest the swing from (4,2) to (12,2) is not possible because you would run into the spider at (10,2).

The goal is, using this swinging through branches method, to travel from the point P to the point Q in the fewest swings possible. For instance, in the example forest, the shortest path is:

1. From (4,2) to (4,8) using (4,5)
2. From (4,8) to (0,8) using (2,8)
3. From (0,8) to (0,0) using (0,4)
4. From (0,0) to (4,0) using (2,0)
5. From (4,0) to (4,10) using (4,5)
6. From (4,10) to (12,10) using (8,10)
7. From (12,10) to (12,2) using (12,6)

Input

Input is from whichever method is convenient (STDIN, command line arguments, raw_input(), etc.), except it may not be pre-initialized as a variable. Input starts with two comma separated integers n and m representing the size of the board, then a space, and then the forest as a single long string. For instance, the example forest as an input would look like this:

15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------

Output

Output a space-separated list of comma separated tuples indicating the coordinates of the branches that you must swing to. For instance, for the above input the output would be:

4,5 2,8 0,4 2,0 4,5 8,10 12,6

You may have noticed that this is not the only shortest path through the forest - indeed, going to (8,8), down to (8,0), left to (4,0) and continuing as normal from there takes exactly the same number of swings. In these cases, your program may output either of the shortest paths. So the output:

4,5 6,8 8,4 6,0 4,5 8,10 12,6

is also allowed. This is code-golf, so the entry with the shortest number of bytes wins. If you have questions or my explanation is not clear, ask in the comments.

Answer 1

GolfScript, 196 characters

' '/(~):H;,):W(\~/-1%'*':S*:^{:I,,{I=79>},:A{{[\1$1$+2/]}+A/}%{)I=43=\$.~I<>S&!\~+1&!&&},}:C~S^W/zip*C{{.H/\H%W*+}%}%+:B;^'P'?]]{{(B{0=1$=},\;\`{\1>\+}+/}%.{0=^=81=},:|!}do;|0=1>-1%{.W%','@W/' '}/

A horrible piece of GolfScript code - however it works as desired. The algorithm is not optimal but fairly fast, the example is running well below a second on my computer.

> 15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------
4,5 2,8 0,4 2,0 4,5 8,10 12,6