Ejercicios recomendados de BFS

Mi solución del problema de buscaminas ```python from collections import deque def actualizarTablero(tablero, clic): fila, columna = clic if tablero[fila][columna] == 'M': tablero[fila][columna] = 'X' else: bfs(tablero, fila, columna) return tablero def bfs(tablero, fila_inicio, columna_inicio): cola = deque([(fila_inicio, columna_inicio)]) while cola: fila, columna = cola.popleft() if tablero[fila][columna] == 'E': minas = contarMinas(tablero, fila, columna) if minas == 0: tablero[fila][columna] = 'B' for i in range(fila - 1, fila + 2): for j in range(columna - 1, columna + 2): if 0 <= i < len(tablero) and 0 <= j < len(tablero[0]): cola.append((i, j)) tablero[i][j] = 'B' # Marcar como visitado else: tablero[fila][columna] = str(minas) def contarMinas(tablero, fila, columna): minas = 0 for i in range(fila - 1, fila + 2): for j in range(columna - 1, columna + 2): if 0 <= i < len(tablero) and 0 <= j < len(tablero[0]) and tablero[i][j] == 'M': minas += 1 return minas # Ejemplo de uso tablero = [ ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'M', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'] ] clic = [3, 0] resultado = actualizarTablero(tablero, clic) for fila in resultado: print(fila) ```from collections import deque def actualizarTablero(tablero, clic): fila, columna = clic if tablero\[fila]\[columna] == 'M': \# Caso 1: Mina revelada, el juego termina tablero\[fila]\[columna] = 'X' else: \# Caso 2: Casilla vacía revelada, utilizar BFS bfs(tablero, fila, columna) return tablero def bfs(tablero, fila\_inicio, columna\_inicio): cola = deque(\[(fila\_inicio, columna\_inicio)]) while cola: fila, columna = cola.popleft() if tablero\[fila]\[columna] == 'E': minas = contarMinas(tablero, fila, columna) if minas == 0: \# Caso 2.1: Casilla vacía sin minas adyacentes tablero\[fila]\[columna] = 'B' for i in range(fila - 1, fila + 2): for j in range(columna - 1, columna + 2): if 0 <= i < len(tablero) and 0 <= j < len(tablero\[0]): cola.append((i, j)) tablero\[i]\[j] = 'B' # Marcar como visitado else: \# Caso 2.2: Casilla vacía con al menos una mina adyacente tablero\[fila]\[columna] = str(minas) def contarMinas(tablero, fila, columna): minas = 0 for i in range(fila - 1, fila + 2): for j in range(columna - 1, columna + 2): if 0 <= i < len(tablero) and 0 <= j < len(tablero\[0]) and tablero\[i]\[j] == 'M': minas += 1 return minas \# Ejemplo de uso tablero = \[ \['E', 'E', 'E', 'E', 'E'], \['E', 'E', 'M', 'E', 'E'], \['E', 'E', 'E', 'E', 'E'], \['E', 'E', 'E', 'E', 'E'] ] clic = \[3, 0] resultado = actualizarTablero(tablero, clic) for fila in resultado: print(fila)

Les comparto mi solución del problema de serpientes y escaleras.

def a_numero(actual: tuple[int], filas: int, columnas: int) -> int:
    f, c = actual
    filas_anteriores = filas - 1 - f
    direccion_actual = 1 if (filas-f)%2 == 1 else -1 # 1 a izq, -1 a der
    columnas_anteriores = c+1 if direccion_actual == 1 else columnas-c

    return filas_anteriores * columnas + columnas_anteriores

def a_posicion(numero: int, filas: int, columnas: int) -> tuple[int]:
    filas_anteriores = int((numero-1) / columnas)
    fila = filas - 1 - filas_anteriores
    direccion = 1 if (filas-fila)%2 == 1 else -1 # 1 a izq, -1 a der
    columnas_anteriores = (numero-1) % columnas
    columna = columnas_anteriores if direccion == 1 else columnas-1-columnas_anteriores

    return (fila, columna)

def serpientes_escaleras(tablero: list[list[int]]) -> int:
    ROWS, COLS = len(tablero), len(tablero[0])
    n2 = ROWS * COLS

    cola = [(ROWS-1, 0)]
    num_pasos  = 0

    while cola:
        for _ in range(len(cola)):
            actual = cola.pop(0)
            actual_numero = a_numero(actual, ROWS, COLS)
            posibles_pasos = range(1,7)

            for paso in posibles_pasos:
                nuevo_numero = actual_numero + paso
                if nuevo_numero < n2:
                    f, c = a_posicion(nuevo_numero, ROWS, COLS)
                    valor_casilla = tablero[f][c]
                    if valor_casilla == -1:
                        cola.append((f, c))
                    else:
                        cola.append(a_posicion(valor_casilla, ROWS, COLS))
                else:
                    return num_pasos+1
        num_pasos += 1

    return -1