AAlgoLoopSpaced repetition for LeetCode
MEDIUMBFS / DFSLeetCode ↗

Snakes and Ladders

The key idea

Treat each square as a graph node and every dice roll (+1 to +6) as an edge to the next 6 squares, applying any snake or ladder to the landing square. Because all edges cost one move, breadth-first search from square 1 finds the minimum number of moves to reach square n * n. The only real work is mapping a square number back to its (row, col) on the boustrophedon (zig-zag) board.

Problem

You are given an n x n integer matrix board where the squares are labeled from 1 to n * n in a boustrophedon (zig-zag) style starting from the bottom-left of the board and alternating direction each row.

You start on square 1. In each move, you roll a 6-sided die and may advance to any square numbered curr + 1 through curr + min(curr + 6, n * n). If a destination square has a snake or ladder, you must move to that snake or ladder's destination; otherwise you move to the destination square. A square has a snake or ladder when board[r][c] is not -1. You may not take more than one snake or ladder per move, even if the landing square is the start of another.

Return the least number of moves required to reach the square n * n. If it is not possible to reach the square, return -1.

Constraints

Examples

Input: board = [[-1,-1],[-1,3]] Output: 1
Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4

Complexity

Time: O(n^2) Space: O(n^2)

See the full solution

410310
Step-by-step visualization
Start free →

More BFS / DFS problems