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
nextcon 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
nexttiene una serpiente o escalera, debes moverte al destino de esa serpiente o escalera. De lo contrario, te mueves anext. - 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 es2. Sigues la escalera a la casilla3, pero no sigues la escalera subsiguiente a4.
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:

Ejemplo 2:
Input: board = [[-1,-1],[-1,3]] Output: 1Soluciones
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