Overview

Within a connected component of V (an underground waterway), you can move freely in \(0\) minutes.
Therefore, we compress each underground waterway into a single vertex and solve it as a shortest path problem on a weighted graph using Dijkstra’s algorithm.

Analysis

Moving between regular cells incurs the following costs:

• Moving to a regular cell such as O, S, G: \(1\) minute
• Moving normally to a V cell: normal movement \(1\) minute + additional underwater movement \(1\) minute = \(2\) minutes
• Moving between V cells within the same underground waterway: \(0\) minutes

Because of this, a simple BFS cannot solve the problem correctly.
BFS works when all edge weights are the same, but since the weights in this problem are \(1\), \(2\), and \(0\), we need Dijkstra’s algorithm or similar.

Also, even though you can move to any V cell within the same underground waterway in \(0\) minutes, adding edges between all pairs of V cells would require \(O(K^2)\) edges if a single waterway contains \(K\) V cells, which is too slow.

The key observation is as follows:

If you are within the same underground waterway, there is no need to distinguish which V cell you are on.

This is because you can move to any V cell within the same waterway in \(0\) minutes.
Therefore, we can treat an entire underground waterway as a single “waterway node.”

For example, when entering an underground waterway from a regular cell:

• This is a move from a regular cell \(\rightarrow\) a V cell, so the cost is \(2\).

On the other hand, when exiting from an underground waterway to an adjacent regular cell:

• This is a move from a V cell \(\rightarrow\) a regular cell, so the cost is \(1\).

In other words, using waterway nodes, we can represent:

• Regular cell \(\rightarrow\) waterway node: cost \(2\)
• Waterway node \(\rightarrow\) adjacent regular cell: cost \(1\)

This compression eliminates the need to add a large number of \(0\)-cost edges.

Algorithm

First, perform DFS/BFS on all V cells to find the connected components of the underground waterways.

For each underground waterway, record the following:

• The component number for the V cells belonging to that waterway
• The set of passable non-V cells adjacent to that waterway

The latter is used as the destinations when exiting the waterway.
In the code, this is stored as boundaries.

Next, consider the following graph and run Dijkstra’s algorithm:

• Each cell is a vertex
• Each underground waterway is an additional vertex
  • The vertex number for waterway \(i\) is N + i
  • Here, \(N = H \times W\)

When a vertex is extracted during Dijkstra’s algorithm, the processing is divided as follows:

When the current vertex is a regular cell

Examine the adjacent cells in four directions (up, down, left, right):

• If it is a wall X, movement is not possible
• If the adjacent cell is V, transition to the waterway node that the V belongs to with cost \(2\)
• If the adjacent cell is O, S, or G, transition to that cell with cost \(1\)

When the current vertex is a waterway node

Transition to all passable non-V cells adjacent to that waterway with cost \(1\).

This corresponds to the operation of moving within the waterway in \(0\) minutes to a V cell near an exit, and then exiting to a regular cell in \(1\) minute.

If the vertex whose shortest distance is finalized is G, output that distance.
If G is never reached, output NO.

Complexity

Let \(N = H \times W\).

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Searching for connected components of V takes \(O(N)\).
Both the number of vertices and edges handled by Dijkstra’s algorithm are bounded by \(O(N)\), so the overall complexity is \(O(N \log N)\).

Implementation Notes

• Recursive DFS may cause deep recursion, so iterative DFS using a stack is used instead.

• The grid is handled as a one-dimensional array.

  • Cell number is \(r \times W + c\)
  • Vertical movement is \(\pm W\)
  • Horizontal movement is \(\pm 1\)

• We never transition directly to a V cell; instead, we always transition to the corresponding waterway node.

• The boundary cells boundaries of a waterway may contain duplicates, but since there are at most \(O(N)\) in total, this is not a problem.

  Source Code

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()

---

This editorial was generated by gpt-5.5-xhigh.