103174: [Atcoder]ABC317 E - Avoid Eye Contact

Problem Statement

There is a field divided into a grid of $H$ rows and $W$ columns.
The square at the $i$-th row from the north (top) and the $j$-th column from the west (left) is represented by the character $A_{i, j}$. Each character represents the following.

• . : An empty square. Passable.
• # : An obstacle. Impassable.
• >, v, <, ^ : Squares with a person facing east, south, west, and north, respectively. Impassable. The person's line of sight is one square wide and extends straight in the direction the person is facing, and is blocked by an obstacle or another person. (See also the description at Sample Input/Output $1$.)
• S : The starting point. Passable. There is exactly one starting point. It is guaranteed not to be in a person's line of sight.
• G : The goal. Passable. There is exactly one goal. It is guaranteed not to be in a person's line of sight.

Naohiro is at the starting point and can move one square to the east, west, south, and north as many times as he wants. However, he cannot enter an impassable square or leave the field.
Determine if he can reach the goal without entering a person's line of sight, and if so, find the minimum number of moves required to do so.

Constraints

• $2 \leq H, W \leq 2000$
• $A_{i,j}$ is ., #, >, v, <, ^, S, or G.
• Each of S and G occurs exactly once among $A_{i, j}$.
• Neither the starting point nor the goal is in a person's line of sight.

Input

The input is given from Standard Input in the following format:

$H$ $W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$A_{2,1}A_{2,2}\dots A_{2,W}$
$\vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

Output

If Naohiro can reach the goal without entering a person's line of sight, print the (minimum) number of moves required to do so. Otherwise, print -1.

Sample Input 1

5 7
....Sv.
.>.....
.......
>..<.#<
^G....>

Sample Output 1

15

For Sample Input $1$, the following figure shows the empty squares that are in the lines of sight of one or more people as !.

Let us describe some of the squares. (Let $(i, j)$ denote the square in the $i$-th row from the north and the $j$-th column from the west.)

• $(2, 4)$ is a square in the line of sight of the east-facing person at $(2, 2)$.
• $(2, 6)$ is a square in the lines of sight of two people, one facing east at $(2, 2)$ and the other facing south at $(1, 6)$.
• The square $(4, 5)$ is not in anyone's line of sight. The line of sight of the west-facing person at $(4, 7)$ is blocked by the obstacle at $(4, 6)$, and the line of sight of the east-facing person at $(4, 1)$ is blocked by the person at $(4, 4)$.

Naohiro must reach the goal without passing through impassable squares or squares in a person's line of sight.

Sample Input 2

4 3
S..
.<.
.>.
..G

Sample Output 2

-1

Print -1 if he cannot reach the goal.

问题描述

有一个由$H$行$W$列组成的网格。

• .：空格，可通行。
• #：障碍物，不可通行。
• >、v、<、^：分别表示面向东、南、西、北的人所在的方格。不可通行。人的视线宽度为一格，沿着人面向的方向直线延伸，被障碍物或另一个人阻挡。（参见样例输入/输出1的描述。）
• S：起点。可通行。起点只有一个，并且保证不在任何人的视线内。
• G：目标。可通行。目标只有一个，并且保证不在任何人的视线内。

Naohiro位于起点，可以向东、西、南、北方向移动任意多次，每次移动一格。但是，他不能进入不可通行的方格或离开场地。

判断他是否能够在不进入人的视线的情况下到达目标，如果可以，找出所需的最小移动次数。

约束

• $2 \leq H, W \leq 2000$
• $A_{i,j}$是.、#、>、v、<、^、S或G。
• S和G在$A_{i, j}$中分别出现一次。
• 起点和目标都不在人的视线内。

输入

输入通过标准输入给出，格式如下：

$H$ $W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$A_{2,1}A_{2,2}\dots A_{2,W}$
$\vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

输出

如果Naohiro可以在不进入人的视线的情况下到达目标，请输出所需的（最小）移动次数。否则，输出-1。

样例输入1

5 7
....Sv.
.>.....
.......
>..<.#<
^G....>

样例输出1

15

对于样例输入1，下图显示了至少一个或多个人的视线范围内的空格，用!表示。

让我们描述其中的一些方格。（让$(i, j)$表示从北向南数第$i$行，从西向东数第$j$列的方格。）

• $(2, 4)$是位于$(2, 2)$处面向东的人的视线范围内的方格。
• $(2, 6)$是两个人的视线范围内的方格，一个面向东的人在$(2, 2)$，另一个面向南的人在$(1, 6)$。
• 方格$(4, 5)$不在任何人的视线范围内。面向西的人在$(4, 7)$处的视线被障碍物在$(4, 6)$处阻挡，面向东的人在$(4, 1)$处的视线被人在$(4, 4)$处阻挡。

Naohiro必须在不经过不可通行的方格或人视线范围内的方格的情况下到达目标。

样例输入2

4 3
S..
.<.
.>.
..G

样例输出2

-1

如果他不能到达目标，则输出-1。