Rock Climbing
Time limit2sMemory limit128 MB
Given holds on a wall with a bounded step distance, find the minimum number of moves from (0,0) to reach height y=T using BFS-style shortest path on a reachability graph.
Problem
A rock wall has n holds. Each hold is represented by coordinates (x, y). From the current position (x, y), you may move to another hold (a, b) only if |a - x| <= 2 and |b - y| <= 2.
You start at (0, 0). Using the holds, you want to reach the top of the wall, whose height is y = T. The x-coordinate at the top does not matter. Find the minimum number of moves needed to reach that height.
Input
The first line contains the number of holds n and the target height T. (1 <= n <= 50,000, 1 <= T <= 200,000)
Each of the next n lines contains the coordinates x, y of one hold. Both coordinates are at least 0, and they satisfy x <= 1,000,000 and y <= T. The starting position (0, 0) is not included in the input.
Output
Print the minimum number of moves needed to reach the top. If the top cannot be reached, print -1.