概要

\(H \times W\) のグリッド状のアイスリンクで、障害物（柱）や壁にぶつかるまで止まれないという特殊な移動ルールのもと、スタート地点 \((1, 1)\) からゴール地点 \((H, W)\) への最小移動回数を求める問題です。

考察

この問題は、各マスを「状態（ノード）」、1回の移動を「辺」とみなした最短経路問題として捉えることができます。

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

1回の移動（滑り始めてから止まるまで）のコストは、移動距離に関わらず常に \(1\) です。このように、すべての辺の重みが等しいグラフにおいて最短経路を求めるには、幅優先探索 (BFS) が最適です。

2. 移動のシミュレーション

通常の迷路探索と異なるのは、「隣のマスに移動する」のではなく「障害物か壁にぶつかるまで進み続ける」点です。 あるマス \((r, c)\) から特定の方向（上下左右）に移動する場合、以下の条件を満たす間、座標を更新し続けます。 - 次のマスがリンクの範囲内（\(1 \le r \le H, 1 \le c \le W\)）である。 - 次のマスに柱がない。

この条件から外れた直前のマスが、その移動での停止位置になります。

3. 探索の効率化

一度訪れたことのあるマスに、より多い手数で到達しても意味がありません。そのため、二次元配列 dist[H][W] を用意して、各マスへの最小移動回数を記録し、未訪問のマスのみを探索するようにします。

アルゴリズム

1. 準備:
   • 柱の位置を素早く判定できるよう、二次元配列（またはセット）に記録します。
   • 各マスへの最小移動回数を保持する二次元配列 dist を \(-1\)（未訪問）で初期化します。
   • キュー（deque）を用意し、スタート地点 \((1, 1)\) を追加して dist[1][1] = 0 とします。
2. BFSの実行:
   • キューから現在の座標 \((r, c)\) を取り出します。
   • \((r, c)\) がゴール \((H, W)\) ならば、その時の dist[r][c] を出力して終了します。
   • 上下左右の 4 方向について以下を繰り返します：
     • 現在地からその方向に、壁か柱に当たるまで 1 マスずつ進むシミュレーションを行います。
     • 止まったマスの座標を \((nr, nc)\) とします。
     • dist[nr][nc] が \(-1\) であれば、dist[nr][nc] = dist[r][c] + 1 と更新し、キューに \((nr, nc)\) を追加します。
3. 終了処理:
   • キューが空になってもゴールに到達できなかった場合は、-1 を出力します。

計算量

• 時間計算量: \(O(HW \cdot \max(H, W))\)
  • 状態数はマスの総数 \(O(HW)\) です。
  • 各状態から 4 方向へ滑るシミュレーションに最大 \(O(\max(H, W))\) かかります。
  • 今回の制約（\(H, W \le 100\)）では、最大でも \(100 \times 100 \times 100 = 1,000,000\) 回程度の計算であり、十分に制限時間内に収まります。
• 空間計算量: \(O(HW)\)
  • グリッドの状態（柱の有無）と、各マスへの距離を保持するために \(O(HW)\) のメモリを使用します。

実装のポイント

• 柱の判定: 柱の位置を is_obstacle[r][c] という真偽値の二次元配列で持つことで、移動中の衝突判定を \(O(1)\) で行えます。

• 滑る処理: while ループを使って、「次のマスに行けるか？」を判定し、行けるなら進む、行けないならループを抜けてその場所を停止位置とする、という実装にすると簡潔です。

• 入出力の高速化: Pythonの場合、データ量が多いときは sys.stdin.read().split() などで一括で読み込むと実行速度が向上します。

  ソースコード

import sys
from collections import deque

def solve():
    # Read all input from standard input at once and split by whitespace
    # This is generally faster for competitive programming in Python.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse the dimensions of the rink H, W and the number of pillars N
    H = int(input_data[0])
    W = int(input_data[1])
    N = int(input_data[2])
    
    # Create a 2D grid to store the positions of the pillars
    # Using 1-based indexing (H+1 x W+1) to match the problem's coordinates
    is_obstacle = [[False] * (W + 1) for _ in range(H + 1)]
    for i in range(N):
        r = int(input_data[3 + 2 * i])
        c = int(input_data[3 + 2 * i + 1])
        # Mark the pillar location
        if 1 <= r <= H and 1 <= c <= W:
            is_obstacle[r][c] = True
            
    # dist[r][c] will store the minimum number of moves to reach square (r, c)
    # Initialize with -1 to represent that the square has not been visited yet
    dist = [[-1] * (W + 1) for _ in range(H + 1)]
    
    # Initialize the BFS queue with the starting position (1, 1)
    # Takahashi starts at (1, 1) with 0 moves
    queue = deque([(1, 1)])
    dist[1][1] = 0
    
    # Standard BFS to find the shortest path in an unweighted graph
    while queue:
        r, c = queue.popleft()
        
        # If the current position is the goal (H, W), we've found the minimum moves
        if r == H and c == W:
            print(dist[r][c])
            return
        
        # Takahashi can slide in four directions: Up, Down, Left, Right
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            # Start sliding from the current position (r, c)
            nr, nc = r, c
            
            # Continue sliding in the chosen direction (dr, dc)
            while True:
                tr, tc = nr + dr, nc + dc
                
                # Check if the next square is within the rink boundaries
                # and if it is not blocked by a pillar
                if 1 <= tr <= H and 1 <= tc <= W and not is_obstacle[tr][tc]:
                    # The square is accessible, so update the current position and continue
                    nr, nc = tr, tc
                else:
                    # Takahashi stops if he hits the rink wall or the square before a pillar
                    break
            
            # If the stopping square (nr, nc) has not been visited before,
            # record the distance and add it to the BFS queue
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
                
    # If the BFS finishes without reaching the goal (H, W), output -1
    print("-1")

if __name__ == '__main__':
    solve()

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