Un laberinto nuevo, el mismo recorrido de la clase y ninguna
lista de adyacencia: los vecinos de cada celda se calculan cuando la cola
los pide. Las capas de la amplitud se ven crecer sobre el dibujo.
1. El laberinto y la predicción
Entrada: una cuadrícula con paredes
(#), Jaimico en S y el café en C. Salida:
el mínimo de pasos de S a C, o −1 si no hay camino.
Montaje:
¿A cuántos pasos queda el café?
2. Ejecute y mire las capas
Azul oscuro: la
celda que salió de la cola. Borde ámbar: la celda que se está mirando.
Cada celda alcanzada muestra su distancia.
Cola: vacía
Paso 0 de 0
Las líneas 13 a 15 son la regla de los vecinos: una
suma y una comprobación, en vez de una lista guardada.
3. Una fila por celda que sale de la cola
Turno
Sale
Su distancia
Encola
4. Qué es el grafo
En este grafo implícito, ¿qué es un vértice?
5. Cambiar las reglas del movimiento
Si Jaimico pudiera moverse en diagonal, ¿qué habría que cambiar en el programa?
El grafo sí cambia —cada celda tiene hasta ocho
vecinos en vez de cuatro—, pero el grafo vive en la regla, y la regla es
la tabla. La amplitud, la cola y la marca no saben cuántas direcciones
hay.
6. Para llevarse
Sin solución aquí. El café del segundo laberinto
queda en −1. Modifique distancias para que además devuelva
la lista de las celdas libres a las que no se llegó, y responda:
¿cuánto cuesta esa pasada adicional, y por qué el recorrido ya sabía la
respuesta antes de hacerla?