Overview

On ice, you “cannot stop midway and slide in a straight line until reaching a wall or the square just before a pillar,” so the transitions from each square are only “the squares where you stop after sliding in 4 directions.” By treating this as a graph, we find the minimum number of moves using breadth-first search (BFS).

Key Insight

The key point of this problem is that “one move = starting to slide in a direction and advancing all the way to the square where you can stop.” In other words, even if you try to move up/down/left/right from (r, c), you cannot freely stop at intermediate squares along the way.

• When sliding upward from a square, you stop at one of the following:
  • Just before going outside the board (hitting a wall)
  • Just before entering a square with a pillar (in front of the pillar)

Therefore, the destinations from each square are determined to be at most 4 (the “squares where you stop after sliding” in up/down/left/right directions).
If we consider only these “stopping squares” as vertices, the cost of each move is always 1, so the shortest number of moves can be found with BFS.

If you naively misunderstand that you can “walk one square at a time” and compute the usual shortest path, you will get WA (because you cannot stop midway).
Also, if you don’t properly calculate the “position where you stop after sliding,” you cannot construct transitions and cannot determine the minimum number of moves.

Algorithm

1. Store pillar positions as obs[r][c] (True/False) using 0-indexed coordinates.
2. Let dist[r][c] be “the minimum number of moves to reach (r, c),” initialized to infinity.
3. Put the starting point (0,0) into the queue with dist=0 and perform BFS.
4. Dequeue (r, c), and for each of the 4 directions, do the following:
   • From (r, c), keep advancing in that direction until the next square is out of bounds or is a pillar
   • The square (nr, nc) just before you can no longer advance is “the square where you stop after sliding in that direction”
   • If dist[nr][nc] > dist[r][c] + 1, update it and add to the queue
5. After BFS completes, if dist[H-1][W-1] has been updated, that is the answer; otherwise, output -1.

For example, when sliding to the right, you advance “until the right neighbor is a wall or pillar,” and the stopping position is just before that. This “calculation of the stopping position” is simulated for each transition every time.

Complexity

• Time complexity: \(O(HW(H+W))\)
  Each square enters the queue at most once (when its shortest distance is updated), and upon dequeuing, it slides in 4 directions for at most the length of its row/column (at most \(H\) or \(W\)).
• Space complexity: \(O(HW)\)
  For the pillar array obs, distance array dist, and the queue.

(Since the constraints are \(H,W \le 100\), this implementation is sufficiently fast.)

Implementation Notes

• Use 0-indexed consistently: The input is 1-indexed, so subtracting 1 makes implementation easier.

• Cannot enter pillar squares: Strictly write the condition in the while loop that if the next square is a pillar, you stop there (you cannot advance into the pillar itself).

• Reason for using BFS: Since the cost of each move is always 1, BFS (not Dijkstra) is sufficient to find the minimum number of moves.

• Detecting unreachability: If the distance is not updated (remains at the initial infinity), output -1.

  Source Code

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()

This editorial was generated by gpt-5.2-high.