← Volver a los ejercicios

Super Mario como grafo de estado

Un mapa con dos aldeas (círculos, 1 y 2) y dos castillos (cuadrados, 3 y 4). Mario sale de la aldea 1 y quiere llegar al castillo 4. Tiene una bota que se puede calzar K veces; calzada, tiene carga L, y cada vía recorrida con ella gasta su peso en carga y no consume tiempo. Un estado es (u, l, k): el lugar, la carga que queda y los usos que faltan. Primero se predicen transiciones, y después se sigue el Dijkstra de 10269-super-mario.py sobre los estados.

1. El mapa y las reglas

Parámetros: a = 2 aldeas, b = 2 castillos, L = 5, K = 1. Vías, con su peso: 1–2 (3), 2–3 (4), 3–4 (2), 1–3 (7), 2–4 (6).

2. Predecir la transición

En cada fila se escribe el estado al que se llega y lo que cuesta la transición, o se marca que no se puede.

3. Predecir el resultado

¿Qué número imprime el programa en este mapa?

4. Ejecute el código

Paso 0 de 0
Cola queue
Tiempos conocidos, vis:
Salida:

        
Las tuplas de la cola son (c, u, l, k), ordenadas de menor a mayor. Tachada, una tupla vieja: su tiempo ya no es el de vis. Sale de la cola y se descarta en la línea 35.

5. Para llevarse

Sin solución aquí. Con K = 2 en el mismo mapa, diga cuánto tarda Mario y en qué lugares calza la bota. Después cuente cuántos estados (u, l, k) podría haber en total para este mapa y compare con los que guarda vis al terminar.