概要

アイスリンク上で、柱や壁にぶつかるまで一直線に滑る高橋君が、スタート地点 \((1, 1)\) からゴール地点 \((H, W)\) まで最短何回の移動で到達できるかを求める問題。

考察

この問題では、通常のグリッド上の移動ではなく、「滑る」動きを考える必要があります。つまり、上下左右のいずれかの方向を選んで動き出すと、柱またはマップの端にぶつかるまで止まらずに進みます。

この「滑る」性質により、単純にBFSで1マスずつ探索しても正しい答えは得られません。例えば、あるマスから右に動いても、実際に停止するのはずっと先かもしれません。

また、同じマスを何度も通る可能性があるため、訪問済みかどうかを適切に管理しないと無限ループに陥ります。

このような状況では、「各マスに到達するための最小移動回数」を記録しながらBFSを行うのが有効です。そして、各ステップで「滑って止まる地点」までシミュレートして次の候補とします。

アルゴリズム

本問題は、0-1 BFSやダイクストラ法のような考え方を応用したBFSで解くことができます。

具体的な手順は以下の通りです：

1. スタート位置 \((0, 0)\) をキューに入れ、そのマスへの移動回数を0として記録。
2. キューから現在位置を取り出し、4方向それぞれに対して以下を実施：
   • 方向を決めたら、柱または境界にぶつかるまで滑り続ける。
   • 最終的な停止位置が未訪問であれば、そこまでの移動回数（現在+1）を記録し、キューに追加。
3. ゴール \((H-1, W-1)\) に到達したらその時の移動回数を出力。
4. 探索が終わっても到達できなければ -1 を出力。

このとき、滑る処理はwhileループを使ってシミュレートします。

計算量

• 時間計算量: \(O(H \times W)\)
  各マスにつき最大4方向を試す必要があり、全体で \(H \times W\) マスなので、定数倍を考慮しても十分間に合う範囲です。
• 空間計算量: \(O(H \times W)\)
  訪問済みフラグやBFSのキューのために \(H \times W\) の二次元配列を使用します。

実装のポイント

• 座標系は入力が1-indexedなので、内部では0-indexedに変換しておくと扱いやすい。
• 滑る処理では、「次に進む予定のマス」が壁でも柱でもないことを確認してから実際に更新する。
• 訪問済み判定は、単なるsetより「距離を記録する配列」を使った方が効率的かつ実装しやすい。
• ゴールにたどり着いたら即座に出力を返すことで無駄な探索を省ける。

## ソースコード

```python
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    H = int(data[0])
    W = int(data[1])
    N = int(data[2])
    
    walls = set()
    for i in range(N):
        r = int(data[3 + 2*i]) - 1
        c = int(data[4 + 2*i]) - 1
        walls.add((r, c))
    
    start = (0, 0)
    goal = (H-1, W-1)
    
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFS
    queue = deque()
    queue.append((start[0], start[1], 0))  # (row, col, moves)
    visited = [[-1]*W for _ in range(H)]
    visited[start[0]][start[1]] = 0
    
    while queue:
        r, c, moves = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r, c
            
            # Slide until hit wall or pillar
            while True:
                tr = nr + dr
                tc = nc + dc
                
                # Check boundaries
                if not (0 <= tr < H and 0 <= tc < W):
                    break  # Hit the edge of the grid
                
                # Check pillar
                if (tr, tc) in walls:
                    break  # Hit a pillar
                
                nr, nc = tr, tc
            
            # If not visited or found shorter path
            if visited[nr][nc] == -1:
                visited[nr][nc] = moves + 1
                if (nr, nc) == goal:
                    print(moves + 1)
                    return
                queue.append((nr, nc, moves + 1))
    
    print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。