29. Laberinto aleatorio

Crea una función que genere un laberinto aleatorio utilizando un algoritmo basado en la construcción de un árbol (por ejemplo, Depth-First Search o Prim’s Algorithm adaptado para la generación de laberintos).

La función no necesita dibujar el laberinto gráficamente, sino que debe devolver una representación del laberinto (por ejemplo, una matriz de caracteres donde ’#’ es una pared y ’ ’ es un camino, o una estructura de datos que represente las conexiones entre celdas).

def generar_laberinto_aleatorio(ancho: int, alto: int) -> list[list[str]]:
    # Tu código aquí
    pass

# Ejemplo de un posible laberinto 5x5 (la representación puede variar)
# generar_laberinto_aleatorio(5, 5)
# [
#  ["#", "#", "#", "#", "#"],
#  ["#", " ", " ", " ", "#"],
#  ["#", " ", "#", " ", "#"],
#  ["#", " ", " ", " ", "#"],
#  ["#", "#", "#", "#", "#"]
# ]
# (Esta es una representación muy simplificada. Un laberinto real tendría más paredes y caminos intrincados)

Ratoncito

Implementa la generación de un laberinto. Puedes empezar con todas las celdas como paredes y "excavar" caminos utilizando una aproximación recursiva (DFS) o aleatoria que forme un árbol.

Dragón

Añade un punto de entrada y salida al laberinto. Además, implementa un algoritmo para resolver el laberinto, es decir, encontrar el camino más corto o un camino desde la entrada hasta la salida, y representarlo de alguna manera en la estructura de datos (por ejemplo, con un carácter diferente para el camino solución).