Snakes and Ladders — BFS on Board State

Problem

Given an n x n board with snakes/ladders (-1 = no effect), find minimum dice rolls to reach square n² from square 1.

Approach — BFS with Board Mapping

Map 1-indexed square number → (row, col) accounting for alternating left-right rows. BFS from 1, expand 1-6 dice rolls.

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

Solutions

Python

from collections import deque
class Solution:
    def snakesAndLadders(self, board: list[list[int]]) -> int:
        n=len(board)
        def pos(s):
            r,c=divmod(s-1,n)
            if r%2==0: return n-1-r,c
            else: return n-1-r,n-1-c
        visited={1}; q=deque([(1,0)])
        while q:
            s,moves=q.popleft()
            for d in range(1,7):
                ns=s+d
                if ns>n*n: break
                r,c=pos(ns)
                if board[r][c]!=-1: ns=board[r][c]
                if ns==n*n: return moves+1
                if ns not in visited: visited.add(ns); q.append((ns,moves+1))
        return -1

Complexity

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