← 返回题目列表

AtCoder · awc0094_e

E. 洞穴探险和地下水道

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

分数: 433 分

问题陈述

高桥正在探索一个洞穴。洞穴被表示为一个网格 H 行和 W 列。

每个单元格都是以下之一:

  • S:高桥的起点
  • G:退出
  • O:可通行的正常走廊
  • V: 一条可以通行但充满水的走廊
  • X:一堵无法逾越的墙

仅通过连接形成的连接组件 V 通过上/下/左/右相邻的单元被称为“地下水道”。

Takahashi 可以按任意顺序执行以下操作:

  • 正常移动到相邻的可通过单元格(上、下、左或右)。正常的移动需要 1 分钟。
  • 如果正常移动的目的地是 V 单元格,需要额外的 1 分钟由于涉水。
  • 即使他输入相同 V 小区或同一地下水道多次,额外 每次他进入一个区域都会产生 1 分钟 V 细胞通过正常移动。
  • 如果当前单元格是 V,他可以乘着水流移动到任何地方 V 属于同一地下水道的小区 0 分钟。
  • 由于此移动不是正常移动,因此额外 1 分钟不会产生,即使目的地是 V 细胞。

求从起点移动所需的最短时间 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 是一个长度为的字符串 W 仅包含 S, G, O, V, X
  • 正好有一个 S 在整个网格中
  • 正好有一个 G 在整个网格中

输入

H W
C_1
C_2
:
C_H
  • 第一行包含 H,洞穴的垂直长度,以及 W,洞穴的水平长度,以空格分隔。
  • 以下 H 行每行包含一个字符串 C_i 代表一排洞穴。
  • 的 (1 + i)- 第行包含一个字符串 C_i 长度 W 代表的状态 i从顶部算起的第 3 行。
  • C_i 仅包含 S, G, O, V, X.
  • 正好有一个 S 正好一个 G.

输出

如果可以从 S to 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