DSA problem

Snakes and Ladders

MediumBreadth First Search (BFS)Pattern: Breadth First Search (BFS)top600AmazonMicrosoftGoogleBloombergApple

You are given an n x n integer matrix board representing the cells of a Snakes and Ladders game numbered from 1 to n * n. The numbering is Boustrophedon (boustrophedonically): it starts at the bottom-left corner with cell 1, then alternates direction row by row going up.

You start on square 1. On each move you roll a die showing a number from 1 to 6 and advance to the destination square — that is, the next min(curr + die, n * n) cells. If your destination square has a snake or ladder, you MUST follow it: board[r][c] either equals -1 (no snake or ladder) or a number 1 <= x <= n * n indicating you move to square x. You may only follow one snake or ladder per move (the destination of the follow is final for that turn). Return the minimum number of moves to reach square n * n, or -1 if impossible.

The cleanest way to solve this is to flatten the 2D board into a 1D array flat[1..n*n] so that flat[i] is the snake-or-ladder target of square i (or -1). Then the problem becomes: starting at 1, find the shortest path to n * n in a graph where each square has up to 6 outgoing edges (to i + 1 through i + 6), and a snake or ladder forces a jump to flat[next]. All edges have weight 1, so BFS gives the optimum.

Run BFS with the initial state being square 1 at distance 0. For each popped square, enqueue every unvisited target reachable by dice rolls 1..6, applying snake/ladder transitions. The first time the target n * n is dequeued the distance is the answer. Total complexity is O(n^2) time and O(n^2) space.

Examples

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: From square 1, roll 2 to reach 3, then 6 to reach 9 (which jumps to nothing), etc. An optimal sequence of 4 moves wins the game.

Example 2

Input: board = [[-1,-1],[-1,3]]

Output: 1

Explanation: From square 1, roll 1 to reach square 2 which is a ladder to square 3 (the goal).

Example 3

Input: board = [[1,1,-1],[1,1,1],[-1,1,1]]

Output: -1

Explanation: Every cell except possibly the target has a snake or ladder that loops, so the goal is unreachable.

Constraints

n == board.length == board[i].length
2 <= n <= 20
board[i][j] is either -1 or in the range [1, n * n].
The square 1 does not have any snake or ladder.
The square n * n does not have any snake or ladder.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

bfsgraphshortest-pathmatrix

Browse all DSA problems