Let's play ASCII mini-golf Let's play code golf... by playing golf.

Input

Your input will be a string consisting of #'s, an o, an @, and .'s. For example:

......@..
.....##..
.........
......o..


. - playable golf course (all shots must end on one of these)
# - a barrier (shots cannot go through this)
o - the starting position of your golf ball
@ - the hole

How to Play ASCII Golf

You start at the o. Here is a valid shot from point A to point B:

1) This shot is straight line that can be drawn between A and B (no curved shots).

A....
....B


2) The line AB may not intersect with a # (barrier), e.g.:

A.#.B


It may, however, be tangent to a barrier:

A#
.B


3) (For clarity) You may not bounce shots off barriers or the edge of the golf course.

Output

Print to stdout (or an acceptable equivalent) the minimum number of shots to get the ball into the hole @. If it is not possible, print -1.

Examples

o....@


=&gt; 1

o.#.@


=&gt; -1

o..#
..#@


=&gt; 2 (you can pass through the vertices of a #, but not the edges)

o#...#
.#.#.#
...#.@


=&gt; 4
Python 2, 469
Pretty long, but it's a start:

R=range
def l(c,x,y,z,t):
 f=abs(z-x);g=1-2*(z&lt;x);p=abs(t-y);q=1-2*(t&lt;y);v=r=0
 for i in R(f):
  w=f+(2*i+1)*p
  for j in R(v,(w-1)/2/f+1):r|='.'&gt;c[x+g*i][y+q*j]
  v=w/2/f
 for j in R(v,p+1):r|='.'&gt;c[z][y+q*j]
 return r
def f(c):
 a=&quot;&quot;.join(c);n=len(c[0]);b=len(a);d=[[9**9*l(c,i/n,i%n,j/n,j%n)+1for i in R(b)]for j in R(b)]
 for k in R(b):
  for i in R(b):
   for j in R(b):
    t=d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    if&quot;o@&quot;==a[i]+a[j]:r=t
 return-1if r&gt;9**9else r

Function f takes a list of strings and returns the number of shots.
Test suite:
def test(s,r):
 print&quot;ok&quot;if f(s.split())==r else&quot;fail&quot;

test(&quot;o # @&quot;, -1)
test(&quot;......@.. .....##.. ......... ......o..&quot;, 2)
test(&quot;o....@&quot;, 1)
test(&quot;o.#.@&quot;, -1)
test(&quot;o..# ..#@&quot;, 2)
test(&quot;o#...# .#.#.# ...#.@&quot;, 4)
test(&quot;o### #..# ###@&quot;, 3)
test(&quot;o.## ##.@&quot;, 1)
test(&quot;...o .@#.&quot;, 2)