Overview

On an ice rink, Takahashi slides in a straight line until he hits a pillar or a wall. The problem asks for the minimum number of moves to reach the goal \((H, W)\) from the start \((1, 1)\).

Analysis

In this problem, instead of normal grid movement, we need to consider “sliding” movement. That is, once you choose a direction (up, down, left, or right) and start moving, you keep going without stopping until you hit a pillar or the edge of the map.

Due to this “sliding” property, simply performing BFS one cell at a time won’t give the correct answer. For example, even if you move right from a certain cell, you might actually stop much further ahead.

Also, since the same cell can be passed through multiple times, you can fall into an infinite loop if you don’t properly manage whether a cell has been visited.

In such situations, it is effective to perform BFS while recording “the minimum number of moves to reach each cell”. At each step, we simulate sliding to the stopping point and use it as the next candidate.

Algorithm

This problem can be solved using BFS with an approach similar to 0-1 BFS or Dijkstra’s algorithm.

The specific procedure is as follows:

1. Enqueue the start position \((0, 0)\) and record the number of moves to that cell as 0.
2. Dequeue the current position and for each of the 4 directions, do the following:
   • Once the direction is chosen, keep sliding until hitting a pillar or a boundary.
   • If the final stopping position has not been visited, record the number of moves (current + 1) and add it to the queue.
3. If the goal \((H-1, W-1)\) is reached, output the number of moves at that point.
4. If the search ends without reaching the goal, output -1.

The sliding process is simulated using a while loop.

Complexity

• Time complexity: \(O(H \times W)\)
  We need to try up to 4 directions for each cell, and there are \(H \times W\) cells in total, so even considering constant factors, this is well within the time limit.
• Space complexity: \(O(H \times W)\)
  A two-dimensional array of size \(H \times W\) is used for the visited flags and the BFS queue.

Implementation Notes

• Since the input uses 1-indexed coordinates, converting to 0-indexed internally makes things easier to handle.

• In the sliding process, confirm that the “next cell to move to” is neither a wall nor a pillar before actually updating the position.

• For visited checks, using a “distance recording array” is more efficient and easier to implement than a simple set.

• Returning the output immediately upon reaching the goal avoids unnecessary exploration.

  Source Code

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

This editorial was generated by qwen3-coder-480b.