/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 425 点
問題文
H 行 W 列のグリッド状に分割されたフィールドがあります。
北 (上側) から i 行目、西 (左側) から j 列目のマスは文字 A_{i, j} で表されます。各文字の意味は次の通りです。
.: 空きマス。進入できる。#: 障害物。進入できない。>,v,<,^: それぞれ東・南・西・北を向いている人がいるマス。進入できない。人の視線は 1 マス分の幅を持ち、人が向いている方向にまっすぐ伸び、障害物や別の人に遮られる。(入出力例 1 にある説明も参考にしてください。)S: スタート地点。進入できる。ちょうど 1 ヵ所だけ存在する。人の視線に入っていないことが保証される。G: ゴール地点。進入できる。ちょうど 1 ヵ所だけ存在する。人の視線に入っていないことが保証される。
ナオヒロくんはスタート地点にいて、東西南北への 1 マス分の移動を好きな回数行えます。ただし、進入できないマスへの移動やフィールドの外への移動はできません。
彼が人の視線に一度も入らずにゴール地点に到達できるか判定して、できる場合はそのために最小で何回の移動が必要か求めてください。
制約
- 2 \leq H, W \leq 2000
- A_{i,j} は
.,#,>,v,<,^,S,Gのいずれかである S,Gは A_{i, j} の中にちょうど 1 回ずつ現れる- スタート地点・ゴール地点はともに人の視線に入っていない
入力
入力は以下の形式で標準入力から与えられる。
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....>
出力例 1
15
入力例 1 について、1 人以上の視線に入っている空きマスを ! で表すと次の図のようになります。
いくつかのマスについて具体的に説明すると次のようになります。(ここで、北から i 行目、西から j 列目のマスを (i, j) と表します。)
- (2, 4) は (2, 2) にいる東を向いている人からの視線に入っているマスである。
- (2, 6) は (2, 2) にいる東を向いている人と (1, 6) にいる南を向いている人の 2 人の視線に入っているマスである。
- (4, 5) は誰の視線にも入っていないマスである。(4, 7) にいる西を向いている人の視線は (4, 6) の障害物に遮られていて、(4, 1) にいる東を向いている人の視線は (4, 4) の人に遮られている。
ナオヒロ君は進入できないマス・視線に入っているマスのどちらも通らずにゴール地点へ行く必要があります。
入力例 2
4 3 S.. .<. .>. ..G
出力例 2
-1
ナオヒロ君がゴール地点に到達できない場合は -1 を出力してください。
Score : 425 points
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, orG. - Each of
SandGoccurs 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.