Snakes And Ladders - Leetcode Solution

Snakes and Ladders is a classic board game that involves rolling a dice and moving a token across a board, which is marked with a grid of squares. The board is divided into a number of rows and columns, and the squares are numbered from one to the total number of squares on the board. Some squares have ladders on them, which allow the player to advance to a higher square instantly, while others have snakes on them, which send the player down to a lower square.

The problem statement on LeetCode is to write a function that takes as input a square board of size n x n, where n is between 2 and 20, and a list of pairs of integers that represent the starting and ending positions of ladders and snakes on the board. The function should return the minimum number of moves required to reach the last square on the board, starting from the first square.

The first step in solving this problem is to represent the board and the ladders and snakes as data structures in Python. We can represent the board as a list of lists, where each inner list represents a row of squares on the board. We can initialize this board as follows:

board = [[0] * n for _ in range(n)]

This initializes the board with all squares marked as zero. We can then add the ladders and snakes to the board by setting the appropriate squares to the ending positions of the ladders and snakes. For example, if we have a ladder that starts at square 3 and ends at square 10, we can add this ladder to the board as follows:

board[n - 2 - 2][2] = 10

This sets the square at position (2, 2) on the board to 10, which is the ending position of the ladder. Note that we use n - 2 - 2 because the rows are numbered from the bottom up, and the first row has index n - 1.

Once we have set up the board, we can solve the problem using a breadth-first search (BFS) algorithm. We start by enqueuing the first square (which is numbered 1) onto a queue, along with its distance from the start (which is zero). We then repeat the following until the queue is empty:

• Dequeue the current square and its distance
• If the current square is the last square on the board, return the distance
• For each possible move that can be made from the current square (i.e., rolling a dice and moving that many squares forward), check if the destination square has not been visited before.
• If the destination square has not been visited before, enqueue it onto the queue with its distance from the start (which is the current distance plus one).

We can keep track of the visited squares using a set.

Here's the Python code that implements this algorithm:

from collections import deque

def snakesAndLadders(board, moves=None):
    n = len(board)

    if moves is None:
        moves = {}

    # Add ladders and snakes to the board
    for start, end in moves:
        x, y = map_position(start, n)
        board[x][y] = end

    visited = set()
    queue = deque([(1, 0)])

    while queue:
        square, distance = queue.popleft()

        if square == n * n:
            return distance

        for i in range(1, 7):
            new_square = square + i

            if new_square > n * n:
                break

            x, y = map_position(new_square, n)

            if board[x][y] > 0:
                # There's a ladder or snake at this square
                new_square = board[x][y]

            if new_square not in visited:
                visited.add(new_square)
                queue.append((new_square, distance + 1))

    return -1

def map_position(square, n):
    row = (square - 1) // n
    col = (square - 1) % n

    if row % 2 == 1:
        col = n - 1 - col

    row = n - 1 - row

    return row, col

The snakesAndLadders function takes two arguments: the board and a list of moves. If no moves are provided, it assumes there are no ladders or snakes on the board. The function first adds the ladders and snakes to the board using the map_position function to calculate the row and column indices of the starting and ending squares.

The function then initializes a set of visited squares and a queue of squares to visit, starting with the first square. It then repeatedly dequeues squares from the queue and enqueues their neighbors, as described above, until it finds the last square or the queue is empty.

The map_position function takes a square number and the size of the board, and returns its row and column indices on the board. It assumes that the bottom row of the board is numbered 0 and the top row is numbered n - 1, and that the rows alternate between being filled from left to right and from right to left. This is why it uses the expressions row = n - 1 - row and col = n - 1 - col to flip the row and column indices depending on the row number.

This implementation has a time complexity of O(n^2), since it visits each square on the board at most once, and a space complexity of O(n^2), since it uses a set to store the visited squares and a queue to store the squares to visit.

1