Time Limit: 2 sec / Memory Limit: 128 MB
Problem Statement
AさんとB君は,$N \times M$ の長方形のマス目状の地域に住んでいる.各マス目は道か壁か家のどれかである. この地域は,道が複雑で入り組んでいるので痴漢被害がよく起こることで有名であるため,この地域と外部との境界は全て壁で囲まれており,隔離されている.
B君はなんとなく気が向いたので,Aさんの家を眺めに行くことにした.しかし,不幸なことにB君は明らかに怪しい顔をしているので,Aさんの家に行く途中に少しでも痴漢の疑いがあるような行動を取ったらすぐに捕まってしまうだろう.特に,右手を壁から離して歩くことは絶対にやってはならない.B君は,一瞬たりとも右手を離すことなく,Aさんの家に辿り着くことが出来るだろうか?
B君はつねに上下左右いずれかの方向を向いていて,B君の右手が届く範囲はB君の向いている方向に対して正面,斜め右前,右,斜め右後ろの4マスのみである. B君は,次のいずれかの行動を繰り返す.ただし,これらを同時に行うことは出来ない.
- 前方に壁がない場合,1マス進む.
- 向いている方向を90度右に変える.
- 向いている方向を90度左に変える.
- 右手が接するマスを変える.ただし,この時にB君は右手を離すことが出来ないので,変更前のマスと変更後のマスの間には共通した点を持っていなくてはならない.
Input
入力は以下の形式で与えられる.
$N$ $M$
$S_1$
$S_2$
:
:
$S_N$
$S_i$ ($1 \le i \le N$) は, $M$ 文字の文字列で各文字は次を表す.
- "^","v","<",">"はB君の最初の位置と最初に向いている方向(上下左右の向き)を表す.
- "." は,何もないマスである.B君は,このマスの上を移動することができる.
- "#" は,壁を表す.壁の上を移動することは出来ない.
- "G" はAさんの家の位置を表す.B君は,Aさんの家にたどり着くまで移動を繰り返す.
Constraints
- $1 \le N \le 50$
- $1 \le M \le 50$
- 入力には,文字 "^","v","<",">" のうちいずれかが必ず一つのみ現れる.
- 同様に,入力には,文字 "G" が必ず一つのみ現れる.
- 初期状態では,B君が向いている方向から右の壁にB君の右手が接している.
Output
一度も右手を離さずにAさんの家に辿り着くことが出来る場合には,Aさんの家にたどり着くまでに通った異なるマスの数の最小値を出力せよ. Aさんの家に辿り着くことが出来ない場合には,-1を出力せよ.
Sample Input 1
3 3 G## .#. .<.
Output for the Sample Input 1
4
Sample Input 2
3 3 G## .#. .>.
Output for the Sample Input 2
6
Sample Input 3
3 3 ... .G. .>.
Output for the Sample Input 3
-1
Sample Input 4
4 4 .... .#.G ...# ^#..
Output for the Sample Input 4
8