Snakes and Ladders
mediumGraphs II+20 XPTime limit 2s
A board has squares 1 … n; you start on square 1 and want to land exactly on square n. Each turn you choose the dice value 1 … 6 yourself (you control the dice!) and move forward that many squares — a move that would go past n is not allowed. If you land on the bottom of a ladder or the head of a snake, you immediately move to its other end (only one jump per turn, even if you land on another jump's start).
A jump a b moves you from square a to square b (b > a is a ladder, b < a is a snake). What is the minimum number of turns to reach square n?
Input:
- line 1:
n k - next
klines: a jumpa b
Output: the minimum number of turns, or -1 if square n cannot be reached.
Constraints: 2 ≤ n ≤ 10⁵, 0 ≤ k < n; 1 < a < n, 1 ≤ b ≤ n, a ≠ b; every square starts at most one jump, and no jump ends on a square where another jump starts.
Think about it: squares are nodes; from square x there are up to 6 edges (to x+1 … x+6, after following any jump). Every turn costs 1, so BFS from square 1 gives the answer in O(6n).
Sample input 1
10 2 3 8 9 2
Sample output 1
2
Sample input 2
9 6 2 1 3 1 4 1 5 1 6 1 7 1
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).