分数: 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