概要

氷の上では「途中で止まれず、壁か柱の手前まで一直線に滑る」ため、各マスからの遷移先は「4方向に滑った結果止まるマス」だけになります。これをグラフとみなし、最小移動回数を幅優先探索（BFS）で求めます。

考察

この問題のポイントは、「1回の移動＝ある方向に滑り始めて、止まれるマスまで一気に進む」ことです。つまり、(r, c) から上下左右に動こうとしても、途中のマスを経由して自由に止まることはできません。

• あるマスから上に滑ると、次のいずれかで停止します：
  • 盤面の外に出そうになった直前（壁にぶつかる）
  • 柱のあるマスに入ろうとした直前（柱の手前）

したがって、各マスからの行き先は最大4つ（上下左右の「滑った後に止まるマス」）に決まります。
この「止まるマス」だけを頂点として考えると、各移動のコストは常に1なので、最短手数は BFS で求められます。

素朴に「1マスずつ歩ける」と勘違いして通常の最短路を取ると WA になります（途中で止まれないため）。
また、「滑って止まる位置」をきちんと計算しないと遷移が作れず、最短手数も求まりません。

アルゴリズム

1. 柱の位置を obs[r][c]（True/False）で保持します（0-indexed）。
2. dist[r][c] を「(r, c) に到達する最小移動回数」として、初期値を無限大にします。
3. 始点 (0,0) を dist=0 でキューに入れ、BFS を行います。
4. キューから (r, c) を取り出し、4方向それぞれについて以下を行います：
   • (r, c) からその方向に、次のマスが盤外または柱になるまで進み続ける
   • 進めなくなる直前のマス (nr, nc) が「その方向に滑った結果止まるマス」
   • dist[nr][nc] > dist[r][c] + 1 なら更新してキューへ追加
5. BFS 終了後、dist[H-1][W-1] が更新されていればそれが答え、更新されていなければ -1。

例えば、右方向に滑るなら「右隣が壁 or 柱になるまで」進め、止まる位置はその直前になります。この“止まる位置の計算”を各遷移で毎回シミュレーションしています。

計算量

• 時間計算量: \(O(HW(H+W))\)
  各マスは高々1回（最短距離が更新されたとき）キューに入り、取り出し時に4方向へ最大でその行/列の長さぶん滑る（最大 \(H\) または \(W\)）ため。
• 空間計算量: \(O(HW)\)
  柱配列 obs と距離配列 dist、キューのため。

（制約が \(H,W \le 100\) なので、この実装で十分高速です。）

実装のポイント

• 0-indexed に統一：入力は 1-indexed なので -1 して扱うと実装が楽です。

• 柱マスには入れない：次のマスが柱ならそこで止める（柱自体へは進めない）条件を while ループ内で厳密に書きます。

• BFS を使う理由：各移動のコストが常に 1 なので、ダイクストラではなく BFS で最短手数が求まります。

• 到達不能の判定：距離が更新されない（初期の無限大のまま）なら -1 を出力します。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    H = next(it)
    W = next(it)
    N = next(it)

    obs = [[False] * W for _ in range(H)]
    for _ in range(N):
        r = next(it) - 1
        c = next(it) - 1
        obs[r][c] = True

    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[0][0] = 0
    q = deque([(0, 0)])

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        r, c = q.popleft()
        d = dist[r][c]
        for dr, dc in dirs:
            nr, nc = r, c
            while True:
                tr, tc = nr + dr, nc + dc
                if tr < 0 or tr >= H or tc < 0 or tc >= W:
                    break
                if obs[tr][tc]:
                    break
                nr, nc = tr, tc
            if dist[nr][nc] > d + 1:
                dist[nr][nc] = d + 1
                q.append((nr, nc))

    ans = dist[H - 1][W - 1]
    print(-1 if ans == INF else ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。