SnakeAndLadder.py

# Question link - https://leetcode.com/problems/snakes-and-ladders/

import collections
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        
        # Helper function to convert 1D position to 2D board coordinates
        def get_coordinates(pos):
            # Convert to 0-indexed position
            pos -= 1
            row = n - 1 - (pos // n)
            col = pos % n
            # Handle zigzag pattern
            if (n - 1 - row) % 2 == 1:
                col = n - 1 - col
            return row, col
        
        # Initialize BFS
        q = collections.deque([(1, 0)])  # (position, moves)
        visited = set([1])
        
        while q:
            position, moves = q.popleft()
            
            # Check if reached the end
            if position == n * n:
                return moves
            
            # Try all possible dice rolls (1-6)
            for i in range(1, 7):
                next_pos = position + i
                
                # Skip if out of bounds
                if next_pos > n * n:
                    continue
                
                # Get the board value at this position
                row, col = get_coordinates(next_pos)
                # If there's a snake or ladder, use that destination
                if board[row][col] != -1:
                    next_pos = board[row][col]
                
                # Only process unvisited positions
                if next_pos not in visited:
                    visited.add(next_pos)
                    q.append((next_pos, moves + 1))
        
        return -1  # No solution found