E - Cave Exploration and Underground Waterways Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は洞窟を探検しています。洞窟は H 行 W 列のマス目で表されます。

各マスは次のいずれかです。

  • S: 高橋君の開始地点
  • G: 出口
  • O: 通行可能な通常の通路
  • V: 通行可能だが、水に浸かった通路
  • X: 通行できない壁

V のマスだけを上下左右の隣接でつないだときの連結成分を「地下水路」と呼びます。

高橋君は、次の行動を任意の順に行うことができます。

  • 上下左右に隣接する通行可能なマスへ通常移動する。通常移動には 1 分かかる。
  • 通常移動の移動先が V の場合、水に浸かりながら進むために追加で 1 分かかる。
  • 同じ V のマスや同じ地下水路に複数回入った場合でも、通常移動で V に入るたびに追加で 1 分かかる。
  • 現在いるマスが V の場合、同じ地下水路に属する任意の V のマスへ、水流に乗って 0 分で移動できる。
  • この移動は通常移動ではないため、移動先が V であっても追加の 1 分はかからない。

開始地点 S から出口 G まで移動するために必要な最小時間を求めてください。

到達できない場合は NO を出力してください。

制約

  • 1 \leq H \leq 10^5
  • 1 \leq W \leq 10^5
  • H \times W \leq 2 \times 10^5
  • C_i は S, G, O, V, X のみからなる長さ W の文字列である
  • S はマス目全体にちょうど 1 つ存在する
  • G はマス目全体にちょうど 1 つ存在する

入力

H W
C_1
C_2
:
C_H
  • 1 行目には、洞窟の縦の長さを表す H と、横の長さを表す W が、スペース区切りで与えられる。
  • 続く H 行では、洞窟の各行を表す文字列 C_i が与えられる。
  • 1 + i 行目では、上から i 行目の状態を表す長さ W の文字列 C_i が与えられる。
  • C_i は S, G, O, V, X のみからなる。
  • S と G はそれぞれちょうど 1 つずつ存在する。

出力

S から G まで移動できる場合は、必要な最小時間を整数で出力してください。移動できない場合は NO を出力してください。

入力例 1

3 5
SOVVG
OOXXO
OOOOO

出力例 1

4

入力例 2

3 3
SXX
XXX
XXG

出力例 2

NO

入力例 3

8 12
SOVVOOOXOOOO
XOXXOXOXOXXO
XOVVVXOVVVXO
XOXOXXOXOXOO
XOXOOOOVOXVX
XOVXXXXVOXVX
XOOOOVVVOXVO
XXXXOOOOOOGX

出力例 3

16

入力例 4

15 20
SOVVVVVOOOOOOOOOOOOO
OXXXXXXOXOOOXOOOXXXO
OOVVVXXOXVVOXOVVVVVO
OXXVXXXOXVXXXXOOXXVO
OXXVVVVOXVOOOOXOXXVO
OOOXXXOOXVXXXXXOXXVO
XVVOOOOXVVVVVVXOXXVO
OVXXXXXXOXXXXOXOXXVO
OVVVVVVOOOOXXOXOOOVO
OXXXXXXOXXOXXOXVXXVO
OOOOOOOOVVOOOOXVXXVO
OXXXXXOXXXXXXXVVXXVO
OVVVVVOOOOOOOOOVVVVO
OXXXXXXXXXXXXXXOXXVO
OOOOOOOOOOXXXXOOOVVG

出力例 4

15

入力例 5

1 2
SG

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is exploring a cave. The cave is represented as a grid with H rows and W columns.

Each cell is one of the following:

  • S: Takahashi's starting point
  • G: The exit
  • O: A passable normal corridor
  • V: A passable but water-filled corridor
  • X: An impassable wall

A connected component formed by connecting only V cells through up/down/left/right adjacency is called an "underground waterway."

Takahashi can perform the following actions in any order:

  • Make a normal move to an adjacent passable cell (up, down, left, or right). A normal move takes 1 minute.
  • If the destination of a normal move is a V cell, it takes an additional 1 minute due to wading through water.
  • Even if he enters the same V cell or the same underground waterway multiple times, the additional 1 minute is incurred each time he enters a V cell via a normal move.
  • If the current cell is V, he can ride the water current to move to any V cell belonging to the same underground waterway in 0 minutes.
  • Since this movement is not a normal move, the additional 1 minute is not incurred even though the destination is a V cell.

Find the minimum time required to move from the starting point S to the exit G.

If it is impossible to reach the exit, output NO.

Constraints

  • 1 \leq H \leq 10^5
  • 1 \leq W \leq 10^5
  • H \times W \leq 2 \times 10^5
  • C_i is a string of length W consisting only of S, G, O, V, X
  • There is exactly one S in the entire grid
  • There is exactly one G in the entire grid

Input

H W
C_1
C_2
:
C_H
  • The first line contains H, the vertical length of the cave, and W, the horizontal length of the cave, separated by a space.
  • The following H lines each contain a string C_i representing a row of the cave.
  • The (1 + i)-th line contains a string C_i of length W representing the state of the i-th row from the top.
  • C_i consists only of S, G, O, V, X.
  • There is exactly one S and exactly one G.

Output

If it is possible to move from S to G, output the minimum time required as an integer. If it is impossible, output NO.

Sample Input 1

3 5
SOVVG
OOXXO
OOOOO

Sample Output 1

4

Sample Input 2

3 3
SXX
XXX
XXG

Sample Output 2

NO

Sample Input 3

8 12
SOVVOOOXOOOO
XOXXOXOXOXXO
XOVVVXOVVVXO
XOXOXXOXOXOO
XOXOOOOVOXVX
XOVXXXXVOXVX
XOOOOVVVOXVO
XXXXOOOOOOGX

Sample Output 3

16

Sample Input 4

15 20
SOVVVVVOOOOOOOOOOOOO
OXXXXXXOXOOOXOOOXXXO
OOVVVXXOXVVOXOVVVVVO
OXXVXXXOXVXXXXOOXXVO
OXXVVVVOXVOOOOXOXXVO
OOOXXXOOXVXXXXXOXXVO
XVVOOOOXVVVVVVXOXXVO
OVXXXXXXOXXXXOXOXXVO
OVVVVVVOOOOXXOXOOOVO
OXXXXXXOXXOXXOXVXXVO
OOOOOOOOVVOOOOXVXXVO
OXXXXXOXXXXXXXVVXXVO
OVVVVVOOOOOOOOOVVVVO
OXXXXXXXXXXXXXXOXXVO
OOOOOOOOOOXXXXOOOVVG

Sample Output 4

15

Sample Input 5

1 2
SG

Sample Output 5

1