← 返回题目列表

AtCoder · abc317_e

H. 避免目光接触

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

分数: 425 点

问题陈述

有一个字段分为以下网格 H 行和 W 列。
广场 i从北数第(顶部)行和 j从西(左)开始的第列由字符表示 A_{i, j}。每个字符代表以下内容。

  • . :一个空的方块。还过得去。
  • # :一个障碍。不可逾越。
  • >, v, <, ^ :一个人分别面向东、南、西、北的方块。不可逾越。人的视线为一平方宽,沿人所面对的方向笔直延伸,并被障碍物或其他人阻挡。 (另请参阅示例输入/输出中的描述 1.)
  • S :起点。还过得去。只有一个起点。保证不在人的视线范围内。
  • G :目标。还过得去。只有一个目标。保证不在人的视线范围内。

直宏位于起点,可以向东、西、南、北移动一格,次数不限。然而,他不能进入无法通行的方格或离开场地。
确定他是否可以在不进入他人视线的情况下到达目标,如果可以,请找到所需的最少移动次数。

约束

  • 2 \leq H, W \leq 2000
  • A_{i,j} is ., #, >, 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,下图显示了一个或多个人视线内的空方块,如下所示 !.

image2

让我们描述一些方块。 (让 (i, j) 表示中的方块 i从北数第 3 行和 j从西数第 3 列。)

  • (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 如果他无法达到目标。