393. Snake and Ladder - Minimum Dice Throws

A snake-and-ladder board has cells numbered 1 to N. Given k snakes/ladders, each as a pair 'a b' meaning landing exactly on cell a instantly moves you to cell b (a ladder if b > a, a snake if b < a; no cell is the start of more than one snake or ladder, and neither endpoint of any snake or ladder is cell 1 or N), find the minimum number of dice throws (each throw moves 1 to 6 cells forward, and a move that would go past cell N is not allowed - you must wait for a smaller roll) needed to go from cell 1 to cell N. Print -1 if it's impossible.

Input: The first line contains N, the number of cells. The second line contains k, the number of snakes/ladders. Each of the next k lines contains two integers a b, meaning landing on cell a moves you to cell b. Output: Print a single integer - the minimum number of dice throws to go from cell 1 to cell N, or -1 if impossible.

2 <= N <= 10^5

A move that would go PAST cell N isn't 'capped' at N - it's simply not a legal move at all and should be skipped entirely, exactly as this problem's statement specifies; miscounting this as a valid capped move is a common bug.

Find the minimum number of dice rolls needed to reach the final cell of a snake-and-ladder board. Brute force: Try every possible sequence of dice rolls via DFS/backtracking, searching for the shortest path to the end - this can revisit the same board positions many times through different roll sequences, far less efficient than BFS's guaranteed shortest-first exploration. Optimised: Since every dice roll counts as ONE move regardless of how far it advances (1 to 6 cells), and snakes/ladders are just instant, cost-free teleports layered on top, this is exactly an unweighted shortest-path problem - BFS naturally finds the minimum number of rolls needed.

Model each cell as a graph node with an edge of weight 1 to every cell reachable by a single dice roll (following any snake or ladder at the destination), then run Dijkstra's algorithm from cell 1 using a priority queue to find the shortest weighted path to cell N. This correctly finds the minimum number of throws and only visits each cell a bounded number of times instead of re-exploring the same states repeatedly, but since every edge has the same weight of 1, the priority queue's ordering work is unnecessary overhead for this particular graph. Time: O(N log N) Space: O(N)

Treat the board as a decision tree: from the current cell, try each of the 6 possible dice rolls, apply any snake or ladder at the resulting cell, and recurse to explore from there, keeping track of throws used and stopping only when cell N is reached or the position is invalid. Taking the minimum over every explored path that reaches N is correct by definition, but without any way to recognize that a cell has already been reached more cheaply through a different sequence of rolls, the same cells get revisited over and over, and the number of distinct roll sequences explodes exponentially with the number of throws. Time: O(6^d) where d is the number of throws in the longest explored path Space: O(d) recursion stack

Because every move costs exactly one dice throw regardless of which of the 1-6 values was rolled, this is an unweighted shortest-path problem, and unweighted shortest paths are exactly what breadth-first search finds without needing a priority queue at all. Starting a BFS from cell 1, exploring the (at most 6) cells reachable by one throw from the current cell (again resolving snakes/ladders at the landing cell) level by level, and stopping the moment cell N is dequeued gives the minimum number of throws directly, with every cell visited exactly once via a simple FIFO queue. Time: O(N) Space: O(N)

1. Treat each cell as a graph node with up to 6 outgoing edges (for dice rolls 1 through 6), all of UNIT weight - this becomes a shortest-path problem on an unweighted graph, solvable with plain BFS from cell 1. 2. The instant a dice roll lands on a cell that starts a snake or ladder, immediately continue from the DESTINATION cell instead - that destination is where the BFS edge should actually point. 3. Discard any dice roll that would go PAST cell N entirely - it's simply not a legal move.

Time: O(N) - each of the N cells is visited and enqueued at most once during the BFS. Space: O(N), for the visited-tracking array and the BFS queue.

Test k = 0 (no snakes or ladders at all), the minimum N = 2, and a board where N is unreachable (expect -1).

Be ready to explain precisely how snakes/ladders are incorporated into the graph model - the EDGE from a cell always points to wherever a dice roll ULTIMATELY lands (after any snake/ladder is applied), not to the raw rolled-to cell itself.