概要

水に浸かった通路（V）の連結成分内は0分で自由に移動できるため、各連結成分を1つのノードに圧縮したグラフを構築し、ダイクストラ法で最短時間を求める問題です。

考察

重要な気づき：V の連結成分は1つのノードとみなせる

同じ地下水路（V の連結成分）内では、水流に乗って 0分 で任意のマスへ移動できます。つまり、一度ある地下水路に入れば、その水路内のどの V マスにいるのかは区別する必要がありません。

素朴なアプローチの問題

各マスをノードとし、V 同士の0コスト辺をすべて張ると、1つの地下水路に \(k\) 個のマスがある場合、\(O(k^2)\) 本の辺が必要になり、TLE の原因になります。

解決策：グラフの圧縮

各地下水路をまとめて 1つの超ノード（スーパーノード） にします。こうすると辺の本数を \(O(H \times W)\) に抑えられます。

辺のコスト設計

圧縮グラフでは、以下の3種類の辺を張ります。

辺の種類	コスト	理由
非Vマス → 隣接する非Vマス	\(1\)	通常移動
非Vマス → 隣接するV成分（超ノード）	\(2\)	通常移動 \(1\) + V進入の追加 \(1\)
V成分（超ノード） → 隣接する非Vマス	\(1\)	成分内で隣接マスまで0分移動 + 通常移動 \(1\)

例えば O → V → V → V → O と移動する場合、圧縮グラフでは O →(2)→ V成分 →(1)→ O となり、合計コスト \(3\) です。これは元のグラフで最初の V に入るコスト \(2\) + 成分内移動 \(0\) + 成分から出るコスト \(1\) と一致します。

アルゴリズム

1. 連結成分の構築: グリッド上の V マスについて BFS で連結成分を求め、各成分に ID を付与する。
2. 圧縮グラフの構築:
   • 非V通行可能マス（S, G, O）はそのまま個別ノード。
   • 各 V 連結成分は1つの超ノード（ノード番号 \(H \times W + \text{成分ID}\)）。
   • 上記の表に従って辺を張る。重複辺は set で排除する。
3. ダイクストラ法: スタート S から G への最短距離を求める。
4. 到達不可能なら NO を出力。

計算量

• 時間計算量: \(O(H \times W \times \log(H \times W))\)
  • 連結成分の BFS: \(O(H \times W)\)
  • グラフの辺数は \(O(H \times W)\) 本
  • ダイクストラ法: \(O(E \log V) = O(H \times W \times \log(H \times W))\)
• 空間計算量: \(O(H \times W)\)

実装のポイント

• 超ノードの番号付け: 通常マスのノード番号を \(r \times W + c\)（\(0\) 〜 \(H \times W - 1\)）、超ノードを \(H \times W + \text{成分ID}\) とすることで、番号が衝突しないようにしています。

• 重複辺の排除: 1つの V 成分が同じ非Vマスに複数箇所で隣接する場合、同じ辺を何本も張ると無駄なので、set で管理して重複を防いでいます。これにより辺数を \(O(H \times W)\) に保てます。

• 辺のコスト \(2\) の意味: 非Vマスから V 成分への辺コスト \(2\) は「通常移動の \(1\) 分 + V マスに入る追加 \(1\) 分」を合算したものです。成分内の移動は \(0\) 分なので、超ノードに到達した時点で成分内のどの V マスにもいられると考えます。

  ソースコード

import sys
from heapq import heappush, heappop
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    H = int(tokens[idx]); idx += 1
    W = int(tokens[idx]); idx += 1
    grid = []
    for i in range(H):
        grid.append(tokens[idx]); idx += 1

    start = end = -1
    for r in range(H):
        for c in range(W):
            if grid[r][c] == 'S':
                start = r * W + c
            elif grid[r][c] == 'G':
                end = r * W + c

    # Find V connected components
    comp = [-1] * (H * W)
    num_comp = 0
    for r in range(H):
        for c in range(W):
            if grid[r][c] == 'V' and comp[r * W + c] == -1:
                cid = num_comp
                num_comp += 1
                q = deque()
                q.append((r, c))
                comp[r * W + c] = cid
                while q:
                    cr, cc = q.popleft()
                    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == 'V' and comp[nr * W + nc] == -1:
                            comp[nr * W + nc] = cid
                            q.append((nr, nc))

    # Build compressed graph
    # Nodes: 0..H*W-1 for non-V passable cells, H*W..H*W+num_comp-1 for V components
    total_nodes = H * W + num_comp
    adj = [[] for _ in range(total_nodes)]

    # Track which (comp_node, neighbor) edges we've already added to avoid duplicates
    comp_to_cell_added = set()
    cell_to_comp_added = set()

    for r in range(H):
        for c in range(W):
            ch = grid[r][c]
            if ch == 'X':
                continue
            if ch == 'V':
                cid = comp[r * W + c]
                comp_node = H * W + cid
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < H and 0 <= nc < W:
                        nch = grid[nr][nc]
                        if nch in ('S', 'G', 'O'):
                            ncell = nr * W + nc
                            key1 = (comp_node, ncell)
                            if key1 not in comp_to_cell_added:
                                comp_to_cell_added.add(key1)
                                adj[comp_node].append((ncell, 1))
                            key2 = (ncell, comp_node)
                            if key2 not in cell_to_comp_added:
                                cell_to_comp_added.add(key2)
                                adj[ncell].append((comp_node, 2))
            else:
                # S, G, O
                cell = r * W + c
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < H and 0 <= nc < W:
                        nch = grid[nr][nc]
                        if nch in ('S', 'G', 'O'):
                            adj[cell].append((nr * W + nc, 1))
                        # V adjacency handled in V branch

    # Dijkstra
    INF = float('inf')
    dist = [INF] * total_nodes
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, u = heappop(heap)
        if d > dist[u]:
            continue
        if u == end:
            print(d)
            return
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heappush(heap, (nd, v))

    if dist[end] < INF:
        print(dist[end])
    else:
        print("NO")

solve()

---

この解説は claude4.6opus-thinking によって生成されました。