We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Snakes and Ladders

Difficulty: Medium

Problem Description

You are given an n x n integer matrix board where the cells are labeled from 1 to n² in a Boustrophedon style starting from the bottom left of the board. You start on square 1 of the board and can choose a destination square in the range [curr + 1, min(curr + 6, n²)]. If the destination has a snake or ladder, you must move to its destination. The game ends when you reach the square n². Return the least number of dice rolls required to reach square n², or -1 if it's not possible.

Key Insights

  • The board is represented in a non-standard way, requiring conversion from 2D coordinates to a 1D representation.
  • The game simulates a 6-sided die, limiting moves to 6 squares ahead.
  • Breadth-First Search (BFS) is suitable for finding the shortest path in an unweighted graph (the board).
  • Snakes and ladders create shortcuts and obstacles, affecting the movement strategy.

Space and Time Complexity

Time Complexity: O(n²) - Each square can be visited once, and each move can result in at most 6 options. Space Complexity: O(n²) - For storing the board state and BFS queue.

Solution

The problem can be solved using a Breadth-First Search (BFS) approach. We treat each square on the board as a node in a graph. The edges represent possible moves based on the die rolls. We maintain a queue to explore each square, tracking the number of rolls taken to reach each square. When processing a square, we check valid moves (up to 6 squares ahead) and apply any snakes or ladders encountered. If we reach the last square, we return the number of moves. If the queue is exhausted without reaching the last square, we return -1.

Code Solutions

from collections import deque

def snakesAndLadders(board):
    n = len(board)
    destination = n * n
    visited = [False] * (destination + 1)
    
    def get_coordinates(square):
        row = (square - 1) // n
        col = (square - 1) % n
        if row % 2 == 1:
            col = n - 1 - col
        return (n - 1 - row, col)
    
    queue = deque([(1, 0)])  # (current square, number of rolls)
    visited[1] = True

    while queue:
        curr, rolls = queue.popleft()
        if curr == destination:
            return rolls
        
        for move in range(1, 7):
            next_square = curr + move
            if next_square > destination:
                continue
            
            r, c = get_coordinates(next_square)
            if board[r][c] != -1:
                next_square = board[r][c]
            
            if not visited[next_square]:
                visited[next_square] = True
                queue.append((next_square, rolls + 1))
    
    return -1
← Back to All Questions