概要

V の連結成分（地下水路）内では \(0\) 分で自由に移動できます。
そこで、各地下水路を 1 つの頂点に圧縮し、重み付きグラフ上の最短路問題として Dijkstra 法で解きます。

考察

通常のマス移動には以下のようにコストがかかります。

• O, S, G などの通常マスへ移動する: \(1\) 分
• V マスへ通常移動する: 通常移動 \(1\) 分 + 水中移動の追加 \(1\) 分 = \(2\) 分
• 同じ地下水路内の V マス同士を移動する: \(0\) 分

このため、単純な BFS では正しく解けません。
BFS はすべての辺の重みが同じ場合に使えるため、重みが \(1\), \(2\), \(0\) と異なるこの問題では Dijkstra 法などが必要です。

また、同じ地下水路内の任意の V マスへ \(0\) 分で移動できるからといって、V マス同士すべてに辺を張ると、1 つの地下水路に \(K\) 個の V マスがある場合に \(O(K^2)\) 本の辺が必要になり、間に合いません。

そこで重要な観察は次の通りです。

同じ地下水路内にいるなら、どの V マスにいるかは区別しなくてよい。

なぜなら、同じ地下水路内なら \(0\) 分で好きな V マスへ移動できるためです。
したがって、地下水路全体を 1 つの「地下水路ノード」として扱えます。

例えば、ある通常マスから地下水路に入る場合は、

• 通常マス \(\rightarrow\) V マスへの移動なのでコスト \(2\)

です。

一方、地下水路から隣接する通常マスへ出る場合は、

• V マス \(\rightarrow\) 通常マスへの移動なのでコスト \(1\)

です。

つまり、地下水路ノードを使うと、

• 通常マス \(\rightarrow\) 地下水路ノード: コスト \(2\)
• 地下水路ノード \(\rightarrow\) 隣接する通常マス: コスト \(1\)

として表せます。

この圧縮により、巨大な \(0\) コスト辺を大量に張る必要がなくなります。

アルゴリズム

まず、すべての V マスについて DFS/BFS を行い、地下水路の連結成分を求めます。

各地下水路について、以下を記録します。

• その地下水路に属する V マスの成分番号
• その地下水路に隣接している通行可能な非 V マスの集合

後者は、地下水路から出る先として使います。
コード中ではこれを boundaries として持っています。

次に、次のようなグラフを考えて Dijkstra 法を行います。

• 各マスを頂点とする
• 各地下水路を追加の頂点とする
  • 地下水路 \(i\) の頂点番号を N + i とする
  • ここで \(N = H \times W\)

Dijkstra 法で頂点を取り出したとき、処理は次のように分かれます。

現在の頂点が通常のマスの場合

上下左右の隣接マスを調べます。

• 壁 X なら移動できない
• 隣接マスが V なら、その V が属する地下水路ノードへコスト \(2\) で遷移
• 隣接マスが O, S, G なら、そのマスへコスト \(1\) で遷移

現在の頂点が地下水路ノードの場合

その地下水路に隣接している通行可能な非 V マスすべてへ、コスト \(1\) で遷移します。

これは、地下水路内で \(0\) 分移動して出口付近の V マスまで行き、そこから通常マスへ \(1\) 分で出る操作に対応します。

最短距離が確定した頂点が G なら、その距離を出力します。
最後まで G に到達できなければ NO を出力します。

計算量

\(N = H \times W\) とします。

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

V の連結成分の探索は \(O(N)\) です。
Dijkstra 法で扱う頂点数・辺数もどちらも \(O(N)\) に抑えられるため、全体で \(O(N \log N)\) です。

実装のポイント

• 再帰 DFS は深さが大きくなる可能性があるため、スタックを使った反復 DFS にしています。

• グリッドは一次元配列として扱っています。

  • マス番号を \(r \times W + c\) とする
  • 上下移動は \(\pm W\)
  • 左右移動は \(\pm 1\)

• V マスへ直接遷移せず、必ず対応する地下水路ノードへ遷移します。

• 地下水路の境界マス boundaries には重複が入る場合がありますが、全体で高々 \(O(N)\) 個なので問題ありません。

  ソースコード

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.buffer.readline
    H, W = map(int, input().split())
    rows = [input().strip() for _ in range(H)]
    grid = b"".join(rows)

    N = H * W
    V = ord("V")
    X = ord("X")

    start = grid.find(b"S")
    goal = grid.find(b"G")

    comp_id = [-1] * N
    boundaries = []

    cid = 0
    Wm1 = W - 1
    NW = N - W

    for i in range(N):
        if grid[i] == V and comp_id[i] == -1:
            comp_id[i] = cid
            stack = [i]
            boundary = []

            while stack:
                v = stack.pop()

                if v >= W:
                    nb = v - W
                    ch = grid[nb]
                    if ch == V:
                        if comp_id[nb] == -1:
                            comp_id[nb] = cid
                            stack.append(nb)
                    elif ch != X:
                        boundary.append(nb)

                if v < NW:
                    nb = v + W
                    ch = grid[nb]
                    if ch == V:
                        if comp_id[nb] == -1:
                            comp_id[nb] = cid
                            stack.append(nb)
                    elif ch != X:
                        boundary.append(nb)

                col = v % W

                if col:
                    nb = v - 1
                    ch = grid[nb]
                    if ch == V:
                        if comp_id[nb] == -1:
                            comp_id[nb] = cid
                            stack.append(nb)
                    elif ch != X:
                        boundary.append(nb)

                if col != Wm1:
                    nb = v + 1
                    ch = grid[nb]
                    if ch == V:
                        if comp_id[nb] == -1:
                            comp_id[nb] = cid
                            stack.append(nb)
                    elif ch != X:
                        boundary.append(nb)

            boundaries.append(boundary)
            cid += 1

    INF = 10**18
    dist = [INF] * (N + cid)
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, node = heappop(pq)
        if d != dist[node]:
            continue

        if node == goal:
            print(d)
            return

        if node < N:
            v = node

            if v >= W:
                nb = v - W
                ch = grid[nb]
                if ch != X:
                    if ch == V:
                        to = N + comp_id[nb]
                        nd = d + 2
                    else:
                        to = nb
                        nd = d + 1
                    if nd < dist[to]:
                        dist[to] = nd
                        heappush(pq, (nd, to))

            if v < NW:
                nb = v + W
                ch = grid[nb]
                if ch != X:
                    if ch == V:
                        to = N + comp_id[nb]
                        nd = d + 2
                    else:
                        to = nb
                        nd = d + 1
                    if nd < dist[to]:
                        dist[to] = nd
                        heappush(pq, (nd, to))

            col = v % W

            if col:
                nb = v - 1
                ch = grid[nb]
                if ch != X:
                    if ch == V:
                        to = N + comp_id[nb]
                        nd = d + 2
                    else:
                        to = nb
                        nd = d + 1
                    if nd < dist[to]:
                        dist[to] = nd
                        heappush(pq, (nd, to))

            if col != Wm1:
                nb = v + 1
                ch = grid[nb]
                if ch != X:
                    if ch == V:
                        to = N + comp_id[nb]
                        nd = d + 2
                    else:
                        to = nb
                        nd = d + 1
                    if nd < dist[to]:
                        dist[to] = nd
                        heappush(pq, (nd, to))

        else:
            nd = d + 1
            for to in boundaries[node - N]:
                if nd < dist[to]:
                    dist[to] = nd
                    heappush(pq, (nd, to))

    print("NO")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-xhigh によって生成されました。