题目描述

有一个被划分为 $H$ 行 $W$ 列的网格状场地。
从北侧（上方）数第 $i$ 行，从西侧（左侧）数第 $j$ 列的格子用字符 $A_{i,j}$ 表示。各字符的含义如下：

• . ：空格，可以进入。
• # ：障碍物，不能进入。
• >、v、<、^ ：分别表示有一个人面朝东、南、西、北站在该格子，不能进入。人的视线宽度为 $1$ 格，会沿着其面朝的方向笔直延伸，直到被障碍物或其他人阻挡为止。（也请参考输入输出样例 $1$ 的说明。）
• S ：起点，可以进入。恰好只出现一次。保证不在任何人的视线范围内。
• G ：终点，可以进入。恰好只出现一次。保证不在任何人的视线范围内。

ナオヒロ君站在起点，可以任意多次向东西南北四个方向移动一格。但不能移动到不可进入的格子，也不能移出场地外。
请判断他是否能在不进入任何人的视线范围的情况下到达终点。如果可以，请求出所需的最小移动次数。

输入格式

输入按以下格式从标准输入给出。

$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}$

输出格式

如果ナオヒロ君能够在不进入任何人的视线范围的情况下到达终点，请输出所需的最小移动次数。如果无法到达，请输出 -1。

样例 1

输入

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

输出

15

样例 2

输入

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

输出

-1

说明/提示

限制条件

• $2 \leq H, W \leq 2000$
• $A_{i,j}$ 只会是 ., #, >, v, <, ^, S, G 这几种字符之一
• S 和 G 在 $A_{i,j}$ 中各出现且仅出现一次
• 起点和终点都保证不在任何人的视线范围内

样例解释 1

对于输入样例 $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)$ 的人阻挡。 ナオヒロ君必须避开不可进入的格子和被视线覆盖的格子，才能到达终点。

样例解释 2

如果ナオヒロ君无法到达终点，请输出 -1。

由 ChatGPT 4.1 翻译