Skills101
← All coding problems

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 k lines: a jump a 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).

Loading editor…

Log in to run and submit your code — it's free.