← 返回题目列表

AtCoder · icpc2014summer_day4_b

B. 可疑人员

中文机器翻译题面 查看原题

问题陈述

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