En UVa 321 The New Villa no hay un grafo dado: los vértices se
construyen. Un estado es el par (habitación, máscara de luces) y de cada estado salen
aristas de peso 1: pasar a una habitación vecina cuya luz esté prendida, o cambiar con un
interruptor la luz de otra habitación. Aquí se ejecuta la función solve de
321-new-villa.cpp sobre una villa pequeña, línea por línea, hasta ver cómo la
búsqueda en amplitud descubre los estados y cómo la meta trae consigo la lista de pasos.
Se empieza en la habitación 1 con solo su luz prendida y se quiere terminar en la última
habitación con solo su luz prendida.
Interruptores: No se cambia la luz de la habitación donde se está.
dist cuando termina el ciclo?
q, de la salida a la entrada: [ ]321-new-villa.cpp. Un estado se
escribe (habitación, {luces prendidas}) y la máscara va en decimal y en binario, con la luz 1 a la
derecha. Las dos líneas for cuentan una vez por cada valor de i.dist| Estado | Máscara | dist | steps que trae |
|---|
dist, que es el orden en que salen de la cola.res la guarda y el ciclo termina. La respuesta se imprime recorriendo res.steps de principio a fin: no hay que reconstruir nada hacia atrás.En la villa sin solución, diga cuál es el último estado
que se descubre y por qué no se puede llegar a la meta. Después compare los estados en
dist de las dos villas en fila: una se detiene antes de explorar todo lo
alcanzable y la otra no. Por último, diga qué cambiaría en los resultados si el ciclo de
puertas se escribiera después del de interruptores.