概要

この問題は、グリッド上の最短経路を求める問題ですが、特定のマス（地下水路 V）の間をコスト \(0\) で自由に移動できるという特殊なルールが特徴です。移動コストが \(0, 1, 2\) の \(3\) 種類存在するため、これらを効率よく処理して最短時間を求めます。

考察

1. 移動コストの整理

問題文のルールを整理すると、隣接するマスへの移動コストは以下のようになります。

• O, S, G への通常移動: コスト \(1\)
• V への通常移動: コスト \(2\) （通常移動 \(1\) + 追加コスト \(1\)）
• 地下水路内の移動: コスト \(0\)
  • 現在地が V のとき、同じ連結成分（地下水路）に属する任意の V へコスト \(0\) で移動できます。

2. 地下水路のワープをどう表現するか

同じ地下水路（V の連結成分）に属するマスが \(K\) 個あるとき、それらすべてのペア（\(K^2\) 個）にコスト \(0\) の辺を張ると、エッジの数が膨大になり制限時間に間に合いません。

これを解決するために、仮想ノードという考え方を使います。 各地下水路（連結成分）ごとに「地下水路ノード」という仮想的な地点を \(1\) つ作ります。 - 各 V マス \(\to\) その地下水路ノード：コスト \(0\) - 地下水路ノード \(\to\) 各 V マス：コスト \(0\)

こうすることで、ある V から別の V へ「V \(\to\) 地下水路ノード \(\to\) V」と経由することで、コスト \(0\) で移動できることを表現できます。エッジの数も V マスの数に比例する程度に抑えられます。

3. 最短経路アルゴリズムの選択

エッジの重みが \(0, 1, 2\) の整数であるため、一般的なダイクストラ法（\(O(E \log V)\)）よりも高速な、0-1-2 BFS（または Dial’s algorithm） を使用することで \(O(V + E)\) で解くことができます。 今回は、現在の距離を \(3\) で割った余りに基づいて \(3\) つのバケツ（キュー）を用意することで、効率的に探索を行います。

アルゴリズム

1. 地下水路のグループ化: BFS または DFS を用いて、隣接する V マスを連結成分としてまとめます。各連結成分に ID を振り、どのマスがどの ID に属するかを記録します。
2. グラフの構築（概念的）:
   • 通常の隣接移動：
     • 移動先が V ならコスト \(2\)、それ以外ならコスト \(1\)。
   • 地下水路のワープ：
     • 各 V マスから対応する仮想ノードへコスト \(0\)。
     • 仮想ノードから各 V マスへコスト \(0\)。
3. 最短経路の計算 (0-1-2 BFS):
   • dist 配列を無限大で初期化し、開始地点 S を \(0\) とします。
   • \(3\) つのバケツ buckets[0, 1, 2] を用意し、buckets[0] に S を入れます。
   • 現在の距離 curr_dist を \(0\) から順に増やしながら、buckets[curr_dist % 3] が空になるまで探索を続けます。
   • 各ノードからの移動先 v について、dist[v] > curr_dist + weight なら dist[v] を更新し、buckets[(curr_dist + weight) % 3] に追加します。
4. 結果の出力:
   • dist[G] が初期値のままなら NO、そうでなければその値を出力します。

計算量

• 時間計算量: \(O(H \times W)\)
  • 地下水路の連結成分の特定に \(O(H \times W)\)。
  • 0-1-2 BFS の各ノード・各エッジの訪問回数は定数回であるため、全体で \(O(H \times W)\) となります。
• 空間計算量: \(O(H \times W)\)
  • グリッドの保持、距離配列、連結成分の情報の保持に必要です。

実装のポイント

• 1次元配列での管理: Python では 2 次元配列 grid[r][c] よりも、1 次元配列 grid[r * W + c] として扱う方がアクセスが高速になり、実行時間を短縮できます。

• 高速な入出力: \(H \times W\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むのが効率的です。

• 仮想ノードのインデックス: マスのインデックスが \(0\) ～ \(HW-1\) なので、仮想ノードのインデックスは \(HW\) 以降に割り当てると管理が楽になります。

  ソースコード

import sys
from collections import deque

def solve():
    # Fast input reading
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    H = int(input_data[0])
    W = int(input_data[1])
    # Join all rows into a single string for 1D grid access
    grid_str = "".join(input_data[2:])
    
    HW = H * W
    start_node = grid_str.find('S')
    goal_node = grid_str.find('G')
    
    # Pre-calculate boolean arrays for faster checks
    is_v = [c == 'V' for c in grid_str]
    is_x = [c == 'X' for c in grid_str]
    
    # comp[i] stores the component ID for each 'V' cell
    comp = [-1] * HW
    comp_count = 0
    comp_cells = []
    
    # Find connected components of 'V' cells using BFS
    for i in range(HW):
        if is_v[i] and comp[i] == -1:
            cells = []
            q = deque([i])
            comp[i] = comp_count
            while q:
                u = q.popleft()
                cells.append(u)
                # Check 4 neighbors in 1D
                # Top
                v = u - W
                if v >= 0 and is_v[v] and comp[v] == -1:
                    comp[v] = comp_count
                    q.append(v)
                # Bottom
                v = u + W
                if v < HW and is_v[v] and comp[v] == -1:
                    comp[v] = comp_count
                    q.append(v)
                # Left
                if u % W != 0:
                    v = u - 1
                    if is_v[v] and comp[v] == -1:
                        comp[v] = comp_count
                        q.append(v)
                # Right
                if u % W != W - 1:
                    v = u + 1
                    if is_v[v] and comp[v] == -1:
                        comp[v] = comp_count
                        q.append(v)
            comp_cells.append(cells)
            comp_count += 1
    
    # 0-1-2 BFS using buckets (Dial's algorithm for small integer weights)
    # dist[0...HW-1] for cells, dist[HW...HW+comp_count-1] for virtual waterway nodes
    inf = 10**18
    dist = [inf] * (HW + comp_count)
    dist[start_node] = 0
    buckets = [[] for _ in range(3)]
    buckets[0].append(start_node)
    
    curr_dist = 0
    
    while True:
        # Stop if all buckets are empty
        if not buckets[0] and not buckets[1] and not buckets[2]:
            break
        
        idx = curr_dist % 3
        bucket = buckets[idx]
        while bucket:
            u = bucket.pop()
            if dist[u] < curr_dist:
                continue
            
            if u < HW:
                # Current node is a cell
                # 1. Option to move to virtual waterway node (weight 0)
                if is_v[u]:
                    v_virt = HW + comp[u]
                    if dist[v_virt] > curr_dist:
                        dist[v_virt] = curr_dist
                        bucket.append(v_virt)
                
                # 2. Normal moves to neighbors (weight 1 or 2)
                u_mod_W = u % W
                # Top neighbor
                v = u - W
                if v >= 0 and not is_x[v]:
                    w = 2 if is_v[v] else 1
                    new_dist = curr_dist + w
                    if dist[v] > new_dist:
                        dist[v] = new_dist
                        buckets[new_dist % 3].append(v)
                # Bottom neighbor
                v = u + W
                if v < HW and not is_x[v]:
                    w = 2 if is_v[v] else 1
                    new_dist = curr_dist + w
                    if dist[v] > new_dist:
                        dist[v] = new_dist
                        buckets[new_dist % 3].append(v)
                # Left neighbor
                if u_mod_W != 0:
                    v = u - 1
                    if not is_x[v]:
                        w = 2 if is_v[v] else 1
                        new_dist = curr_dist + w
                        if dist[v] > new_dist:
                            dist[v] = new_dist
                            buckets[new_dist % 3].append(v)
                # Right neighbor
                if u_mod_W != W - 1:
                    v = u + 1
                    if not is_x[v]:
                        w = 2 if is_v[v] else 1
                        new_dist = curr_dist + w
                        if dist[v] > new_dist:
                            dist[v] = new_dist
                            buckets[new_dist % 3].append(v)
            else:
                # Current node is a virtual waterway node
                # Option to move to any cell in the same waterway (weight 0)
                for v in comp_cells[u - HW]:
                    if dist[v] > curr_dist:
                        dist[v] = curr_dist
                        bucket.append(v)
        curr_dist += 1
            
    ans = dist[goal_node]
    if ans >= inf:
        print("NO")
    else:
        print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。