Snakes and Ladders

909.Snakes and Ladders

Breadth-First Search

Matrix

Graph

Problem Statement:

Given an n x n board of snakes and ladders, where -1 represents an empty cell and any other value represents the destination of a snake or ladder, find the minimum number of moves required to reach the last cell (n²). You can only move 1-6 steps at a time.

Example:

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

Algorithm:

1. Use BFS to find shortest path
2. Convert between 1D and 2D coordinates
3. Handle snake and ladder jumps
4. Track visited cells to avoid cycles

Complexity:

Time: O(n²) | Space: O(n²)

Java Solution:

public int snakesAndLadders(int[][] board) {
    int n = board.length;
    boolean[][] visited = new boolean[n][n];
    Queue<Integer> queue = new LinkedList<>();
    
    // Start from first cell
    queue.offer(0);
    visited[n-1][0] = true;
    int moves = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        // Process current level
        for (int i = 0; i < size; i++) {
            int cell = queue.poll();
            
            // Check if reached destination
            if (cell == n * n - 1) 
                return moves;
            
            // Try all dice rolls
            for (int dice = 1; dice <= 6; dice++) {
                int nextCell = cell + dice;
                if (nextCell >= n * n) continue;
                
                // Convert to 2D coordinates
                int[] coords = getCoordinates(nextCell, n);
                int row = coords[0], col = coords[1];
                
                if (visited[row][col]) continue;
                
                visited[row][col] = true;
                
                // Handle snake or ladder
                if (board[row][col] != -1) {
                    nextCell = board[row][col] - 1;
                }
                
                queue.offer(nextCell);
            }
        }
        moves++;
    }
    
    return -1;
}

private int[] getCoordinates(int cell, int n) {
    // Convert cell number to board coordinates
    int row = n - 1 - cell / n;
    int col = cell % n;
    
    // Handle alternating row direction
    if ((n - 1 - row) % 2 == 1) {
        col = n - 1 - col;
    }
    
    return new int[]{row, col};
}

Python Solution:

def snakesAndLadders(self, board: List[List[int]]) -> int:
    n = len(board)
    visited = set()

    def get_coordinates(cell: int) -> tuple:
        row = n - 1 - (cell - 1) // n
        col = (cell - 1) % n
        if ((n - 1 - row) % 2 == 1):
            col = n - 1 - col
        return (row, col)
    
    q = deque([(1, 0)])  # (position, moves)
    
    while q:
        pos, moves = q.popleft()
        
        # Try all dice rolls
        for next_pos in range(pos + 1, min(pos + 6, n * n) + 1):
            row, col = get_coordinates(next_pos)
            destination = next_pos
            
            # Handle snake or ladder
            if board[row][col] != -1:
                destination = board[row][col]
                
            if destination == n * n:
                return moves + 1
                
            if destination not in visited:
                visited.add(destination)
                q.append((destination, moves + 1))
                
    return -1

C++ Solution:

int snakesAndLadders(vectorint>>& board) {
    int n = board.size();
    vectorbool>> visited(n, vector<bool>(n));
    queue<int> q;
    
    q.push(0);
    visited[n-1][0] = true;
    int moves = 0;
    
    while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; i++) {
            int curr = q.front();
            q.pop();
            
            if (curr == n * n - 1) return moves;
            
            for (int dice = 1; dice <= 6; dice++) {
                int next = curr + dice;
                if (next >= n * n) continue;
                
                int row = n - 1 - next / n;
                int col = next % n;
                if ((n - 1 - row) % 2 == 1) col = n - 1 - col;
                
                if (visited[row][col]) continue;
                
                visited[row][col] = true;
                
                if (board[row][col] != -1) {
                    next = board[row][col] - 1;
                }
                
                q.push(next);
            }
        }
        moves++;
    }
    
    return -1;
}