You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.
You start on square 1 of the board. In each move, starting from square curr, do the following:
next with a label in the range [curr + 1, min(curr + 6, n2)].
next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.n2.A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 are not the starting points of any snake or ladder.
Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.
[[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.Return the least number of dice rolls required to reach the square n2. If it is not possible to reach the square, return -1.
Example 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 Explanation: In the beginning, you start at square 1 (at row 5, column 0). You decide to move to square 2 and must take the ladder to square 15. You then decide to move to square 17 and must take the snake to square 13. You then decide to move to square 14 and must take the ladder to square 35. You then decide to move to square 36, ending the game. This is the lowest possible number of moves to reach the last square, so return 4.
Example 2:
Input: board = [[-1,-1],[-1,3]] Output: 1
Constraints:
n == board.length == board[i].length2 <= n <= 20board[i][j] is either -1 or in the range [1, n2].1 and n2 are not the starting points of any snake or ladder.Problem Overview: You are given an n x n snakes and ladders board where cells are labeled from 1 to n^2 in a boustrophedon (zigzag) order starting from the bottom row. From a cell, you roll a dice (1–6) and move forward. If the destination cell contains a snake or ladder, you must move to its target. The task is to compute the minimum number of dice throws required to reach cell n^2.
Approach 1: Breadth-First Search (BFS) (Time: O(n^2), Space: O(n^2))
This board naturally forms an unweighted graph where each cell is a node and edges represent dice outcomes from +1 to +6. Use Breadth-First Search to explore positions level by level, where each BFS layer corresponds to one dice roll. For every position, simulate the six possible moves, convert the target cell number into its 2D board coordinates, and check whether a snake or ladder redirects the move. Maintain a visited array to avoid revisiting cells. BFS guarantees the first time you reach n^2 is the minimum number of moves because all edges have equal cost. This approach is the standard and most efficient solution.
Approach 2: Dijkstra's Algorithm Adaptation (Time: O(n^2 log(n^2)), Space: O(n^2))
You can also model the board as a weighted graph and apply Dijkstra’s algorithm. Each node represents a board cell and each dice roll produces edges to the next six cells. The weight of each edge is 1 since every dice throw counts as one move. Using a priority queue, repeatedly expand the node with the smallest number of moves so far. Snake or ladder jumps are applied immediately when computing neighbors. Although this works correctly, the extra log factor from the priority queue makes it slower than BFS for this problem because all edges have identical weight. BFS is typically preferred for unweighted graphs.
The tricky part of the implementation is converting a cell number into board coordinates because rows alternate direction. Compute the row using integer division, then reverse the column index for every other row. This mapping step converts the linear position into the correct matrix index.
Recommended for interviews: BFS is the expected solution. It models the board as an unweighted graph and finds the shortest path in O(n^2) time. Showing the BFS traversal with a visited set demonstrates strong understanding of graph traversal on a grid-like structure stored in an array. Mentioning the Dijkstra alternative shows awareness of shortest-path algorithms, but BFS is simpler and optimal here.
The Snakes and Ladders board can be seen as a graph where each square is a node, and an edge exists between node i and node j if you can move from square i to square j with a dice roll. Use BFS to efficiently explore this graph, ensuring each move accounts for ladders and snakes.
The solution flattens the 2D board to a 1D array while considering the Boustrophedon order. Then, using BFS, it processes nodes (squares) ensuring each is visited based on dice moves accounting for any ladders or snakes directly. It effectively exits on reaching the end square.
Time Complexity: O(n^2), where n is the board dimension, as each square is processed once.
Space Complexity: O(n^2), for storing the queue and visited status of squares.
Dijkstra's Algorithm typically finds shortest paths in weighted graphs. Adapting it for an unweighted snakes and ladders board can ensure the fewest moves to reach the final square by evaluating and using priority. Each move is computed implicitly based on its dice-distance weight.
The C implementation uses a modified Dijkstra-like approach with direct BFS priority management via a min-heap to identify the least cost number of rolls to navigate the board to its end.
Time Complexity: O(n^2 log(n^2)), given heap operations for prioritized traversal.
Space Complexity: O(n^2) for heap management.
We can use the Breadth-First Search (BFS) method, starting from the starting point, moving forward 1 to 6 steps each time, and then checking for snakes or ladders. If there are any, move to the destination of the snake or ladder; otherwise, move to the next square.
Specifically, we use a queue q to store the current reachable square numbers, initially putting number 1 into the queue. At the same time, we use a set vis to record the squares that have been reached to avoid revisiting them, initially adding number 1 to the set vis.
In each operation, we take out the square number x at the front of the queue. If x is the endpoint, we can return the current number of steps. Otherwise, we move x forward 1 to 6 steps, setting the new number as y. If y falls outside the board, we skip it directly. Otherwise, we need to find the row and column corresponding to y. Since the row numbers decrease from bottom to top, and the column numbers depend on the parity of the row, we need to perform some calculations to get the row and column corresponding to y.
If the square corresponding to y has a snake or ladder, we need to move to the destination of the snake or ladder, denoted as z. If z has not been visited, we add z to the queue and set, allowing us to continue the breadth-first search.
If we ultimately cannot reach the endpoint, we return -1.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the side of the board.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(n^2), where n is the board dimension, as each square is processed once. Space Complexity: O(n^2), for storing the queue and visited status of squares. |
| Dijkstra's Algorithm Adaptation | Time Complexity: O(n^2 log(n^2)), given heap operations for prioritized traversal. Space Complexity: O(n^2) for heap management. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n^2) | O(n^2) | Best choice for this problem since the board forms an unweighted graph and BFS guarantees the shortest path in dice rolls. |
| Dijkstra's Algorithm Adaptation | O(n^2 log(n^2)) | O(n^2) | Useful if edges had different weights; works here but adds unnecessary priority queue overhead. |
Snakes and Ladders - Leetcode 909 - Python • NeetCode • 75,323 views views
Watch 9 more video solutions →Practice Snakes and Ladders with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor