← Volver a los ejercicios

La cuadrícula como grafo

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

TurnoSaleSu distanciaEncola

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?