问题陈述
A先生和B君住在一个 $N imes M$ 的长方形格子状区域。每个格子要么是道路,要么是墙壁,要么是房子。 由于这个区域道路复杂且容易迷路,因此性骚扰事件频发,人们都知道这一点,所以该区域与外部的边界全部被墙壁围住,形成隔离。
B君出于某种心血来潮,决定去眺望一下A先生的家。然而,不幸的是,B君看起来明显很可疑,所以如果他在前往A先生家途中表现出哪怕一丝可能引起性骚扰嫌疑的行为,肯定会立刻被抓住。特别是,绝对不能走出离墙太远的路线。B君是否能够一边不离开右前方向一瞬间,顺利到达A先生的家呢?
B先生总是面向上、下、左或右,右肩的活动范围限制在B面向的四个点:前方、右前斜、右和后斜。 B重复以下动作之一。但你不能同时完成所有这些动作。
- 如果前方没有墙,前进1步。
- 把你面向的方向向右转90度。
- 把你面向的方向向左转90度。
- 改变右肩接触处的方格。然而,由于B此时不放开右肩,变换前后方格之间必定存在一个共同点。
输入
输入格式如下。
$N$ $M$
$S_1$
$S_2$
:
:
$S_N$
$S_i$($1 \le i \le N$)是一串$M$字符,每个字符代表以下内容。
- "^","v","<",">“这代表B的初始位置和他最初面向的方向(垂直方向)。
- ".是一个什么都没有的格子。B君可以在这个格子上移动。
- "#”代表一堵墙。你不能在墙上移动。
- "G”代表A先生家的位置。 B 先生继续前行,直到到达 A 先生的家。
约束
- $1 \le N \le 50$
- $1 \le M \le 50$
- 对于输入,字符“^","v","<",">“始终只出现其中之一。
- 同样,对于输入,字符“G“总是出现一次。
- 在初始状态下,B的右手从B面向的方向触摸右侧的墙壁。
输出
如果你可以在不放开右手的情况下到达 A 先生的家,请打印出到达 A 先生家时经过的不同方格的最少数量。 如果你无法到达A先生的家,则输出-1。
示例输入 1
3 3 G## .#. .<.
样本输入 1 的输出
4
示例输入 2
3 3 G## .#. .>.
样本输入 2 的输出
6
示例输入 3
3 3 ... .G. .>.
样本输入 3 的输出
-1
示例输入 4
4 4 .... .#.G ...# ^#..
样本输入 4 的输出
8