概要

滑りやすいアイスリンク上で、スタート地点からゴールまで到達するための最小移動回数を求める最短経路問題です。一度滑り出すと壁か柱の手前まで止まれないという特殊な移動ルールがあります。

考察

問題の特徴

この問題の最大のポイントは「一度滑り出すと止まれない」という移動ルールです。

例えば、\(5 \times 5\) のリンクで \((1, 1)\) から右に滑り出すと、途中に柱がなければ \((1, 5)\)（右端の壁）まで一気に移動します。もし \((1, 3)\) に柱があれば、\((1, 2)\)（柱の直前）で止まります。

なぜ BFS が使えるか

• 各移動のコストは「1回」で均一
• 最小移動回数を求めたい

このような問題では 幅優先探索（BFS） が最適です。BFS は各状態に最初に到達したときが最短距離であることが保証されます。

状態の定義

状態は単純に「現在の座標 \((r, c)\)」で表現できます。同じマスに同じ移動回数で複数回到達する必要はないため、訪問済みの管理が可能です。

アルゴリズム

1. 初期化: スタート地点 \((1, 1)\) をキューに入れ、距離を \(0\) とする

2. BFS のメインループ:

   • キューから現在位置 \((r, c)\) を取り出す
   • 上下左右の 4 方向それぞれについて、滑った先の位置を計算する
     • 壁（リンクの端）にぶつかるまで、または柱の直前まで進む
   • 滑った先が未訪問なら、距離を記録してキューに追加
   • ゴールに到達したら、その距離を出力して終了

3. 滑る処理の詳細:

   現在位置 (nr, nc) から方向 (dr, dc) に1マスずつ進む
   while True:
      次の位置 = (nr + dr, nc + dc)
      if 次の位置が壁の外 or 次の位置に柱がある:
          break  # 現在位置で止まる
      nr, nc = 次の位置  # 移動を続ける
   

4. 終了条件: キューが空になってもゴールに到達できなければ -1 を出力

計算量

• 時間計算量: \(O(H \times W \times \max(H, W))\)

  • 各マスは高々 1 回キューに入る: \(O(H \times W)\) 通りの状態
  • 各状態から 4 方向に滑る処理で、最大 \(O(\max(H, W))\) マス進む

• 空間計算量: \(O(H \times W)\)

  • 距離を記録する辞書（または配列）のサイズ
  • 柱の位置を記録するセットのサイズ: \(O(N)\)

制約が \(H, W \leq 100\) なので、最悪でも約 \(10^6\) 程度の計算量となり、十分高速に動作します。

実装のポイント

1. 柱の位置は Set で管理: 柱があるかどうかの判定を \(O(1)\) で行うため、set を使用します。

2. 滑った結果が元の位置と同じ場合をスキップ: 壁が隣接していて実際には動けない場合、無駄な処理を避けます。

3. ゴール到達時の早期終了: BFS では最初にゴールに到達したときが最短なので、即座に答えを出力できます。

4. 座標は 1-indexed: 問題文に合わせて座標を 1 から始めることで、壁の判定が < 1 または > H（> W）と直感的に書けます。

   ソースコード

from collections import deque

def solve():
    H, W, N = map(int, input().split())
    
    # 柱の位置を記録
    pillars = set()
    for _ in range(N):
        r, c = map(int, input().split())
        pillars.add((r, c))
    
    # BFSで最短経路を探索
    # 状態: (行, 列)
    start = (1, 1)
    goal = (H, W)
    
    if start == goal:
        print(0)
        return
    
    # 距離を記録
    dist = {}
    dist[start] = 0
    
    queue = deque([start])
    
    # 方向: 上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        r, c = queue.popleft()
        current_dist = dist[(r, c)]
        
        for dr, dc in directions:
            # その方向に滑り続ける
            nr, nc = r, c
            while True:
                next_r, next_c = nr + dr, nc + dc
                # 壁にぶつかるか確認
                if next_r < 1 or next_r > H or next_c < 1 or next_c > W:
                    # 壁にぶつかった、現在位置で止まる
                    break
                # 柱があるか確認
                if (next_r, next_c) in pillars:
                    # 柱の直前で止まる
                    break
                # 移動可能
                nr, nc = next_r, next_c
            
            # 滑った結果の位置
            if (nr, nc) != (r, c):  # 実際に移動した場合
                if (nr, nc) not in dist:
                    dist[(nr, nc)] = current_dist + 1
                    if (nr, nc) == goal:
                        print(current_dist + 1)
                        return
                    queue.append((nr, nc))
    
    # ゴールに到達できない
    print(-1)

solve()

---

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