Snake and Ladder Problem

'''
T.C O(N) ie. no. of blocks
Logic:
->We will use bfs here.snl


the firs tip is flat the 2d table to 1d just keep in mind that first row of input is the top of snake and ladder and bottom is the start ie. 1,2,3 and flat the board like 1,2,3...n*n+1
'''

from collections import deque
class Solution:
    def snakesAndLadders(self, board):
        n = len(board)

        # Step 1: Convert board to 1D array
        cells = [-1] * (n * n + 1)
        idx = 1
        left_to_right = True

        for r in range(n - 1, -1, -1): #we are doing here because first bottom row is at end and top row is it in beginning.
            for val in board[r] if left_to_right else reversed(board[r]): #if direction is left to right, we follow as it is else reverse

                # Assign the board value to the current square number
                # val == -1  -> normal square
                # val != -1  -> snake or ladder destination
                cells[idx] = val

                # Move to the next square number
                idx += 1

            # After finishing one row, flip the direction
            # This creates the zig-zag (boustrophedon) pattern
            left_to_right = not left_to_right


        # Step 2: BFS
        queue = deque([(1, 0)])  # (current square, moves)
        visited = set([1])

        while queue:
            curr, moves = queue.popleft()

            for next_sq in range(curr + 1, min(curr + 6, n * n) + 1):
                dest = cells[next_sq] if cells[next_sq] != -1 else next_sq

                if dest == n * n:
                    return moves + 1

                if dest not in visited:
                    visited.add(dest)
                    queue.append((dest, moves + 1))

        return -1