Serpientes y Escaleras

Se te proporciona una matriz de enteros n x n llamada board donde las celdas están etiquetadas del 1 al n² en estilo Bustrofedon comenzando desde la esquina inferior izquierda del tablero (es decir, board[n - 1][0]) y alternando la dirección en cada fila.

Comienzas en la casilla 1 del tablero. En cada movimiento, comenzando desde la casilla curr, haz lo siguiente:

  • Elige una casilla de destino next con una etiqueta en el rango [curr + 1, min(curr + 6, n²)].
    • Esta elección simula el resultado de una tirada de dado estándar de 6 caras: es decir, siempre hay como máximo 6 destinos, independientemente del tamaño del tablero.
  • Si next tiene una serpiente o escalera, debes moverte al destino de esa serpiente o escalera. De lo contrario, te mueves a next.
  • El juego termina cuando alcanzas la casilla n².

Una casilla del tablero en la fila r y columna c tiene una serpiente o escalera si board[r][c] != -1. El destino de esa serpiente o escalera es board[r][c]. Las casillas 1 y n² no son puntos de inicio de ninguna serpiente o escalera.

Ten en cuenta que solo tomas una serpiente o escalera como máximo una vez por tirada de dados. Si el destino de una serpiente o escalera es el inicio de otra serpiente o escalera, no sigues la serpiente o escalera subsiguiente.

  • Por ejemplo, supón que el tablero es [[-1,4],[-1,3]], y en el primer movimiento, tu casilla de destino es 2. Sigues la escalera a la casilla 3, pero no sigues la escalera subsiguiente a 4.

Devuelve el menor número de tiradas de dados requeridas para alcanzar la casilla n². Si no es posible alcanzar la casilla, devuelve -1.

Ejemplos

Ejemplo 1:

Figura 1: Tablero de juego
Tablero de juego
Input: board = [[-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,-1], [-1,35,-1,-1,13,-1], [-1,-1,-1,-1,-1,-1], [-1,15,-1,-1,-1,-1]] Output: 4 Explicación: - Al principio, comienzas en la casilla 1 (en la fila 5, columna 0). - Decides moverte a la casilla 2 y debes tomar la escalera a la casilla 15. - Luego decides moverte a la casilla 17 y debes tomar la serpiente a la casilla 13. - Luego decides moverte a la casilla 14 y debes tomar la escalera a la casilla 35. - Luego decides moverte a la casilla 36, terminando el juego. - Este es el menor número posible de movimientos para alcanzar la última casilla, así que devuelve 4.

Ejemplo 2:

Input: board = [[-1,-1],[-1,3]] Output: 1

Soluciones

Python
from collections import deque

class Solution:
    
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        
        n = len(board)
        MAX = n * n
        q = deque([1])
        visited = [False] * (MAX + 1)
        visited[1] = True
        
        level = 0
        while q:
            size = len(q)
            for _ in range(size):
                curr = q.popleft()
                
                if curr == MAX:
                    return level
                
                for next_pos in range(curr + 1, min(curr + 6, MAX) + 1):
                    dest = next_pos
                    # Calcular posición en el tablaro
                    row = (next_pos - 1) // n
                    col = (next_pos - 1) % n
                    if row % 2 == 1:  # filas impares van de derecha a izquierda
                        col = n - 1 - col
                    
                    row = n - 1 - row  # Convertir a coordenadas del tablero
                    
                    if board[row][col] != -1:
                        dest = board[row][col]
                    
                    if not visited[dest]:
                        visited[dest] = True
                        q.append(dest)
            level += 1
        return -1
BUSCARCtrl K