Kareleseo

Estando en el país de Creta, Kareleseo se vio en la necesidad de derrotar al minotauro del laberinto. El minotauro vive en el centro de un laberinto formado por cuadrados concéntricos, es decir, uno dentro otro. Los cuadrados tienen ancho uno y están limitados por paredes. Cada cuadrado está conectado con el cuadrado inmediatamente menor por exactamente dos puertas. Cada una de estas puertas tiene un ancho exactamente de uno y pueden estar colocadas en cualquier lugar a lo largo de la pared que une ambos cuadrados. Las puertas nunca están en las esquinas. El cuadrado exterior del laberinto no tiene ninguna puerta en su pared externa.

Muchos antes que Kareleseo han intentado sin éxito recorrer el laberinto para derrotar al minotauro. El secreto de Kareleseo, será dejar un hilo amarrado para no perderse. Para no arriesgarse a que se termine el hilo, Kareleseo quiere tomar, en cada cuadrado, el camino más corto que lo lleve a una de las puertas que conectan con el siguiente cuadrado.

Escribe un programa que le ayude a Kareleseo a, en cada cuadrado, encontrar la puerta más cercana que lo lleva al siguiente cuadrado hasta llegar al minotauro.

Kareleseo deberá dejar un camino de montones de 1 zumbador desde su posición inicial hasta el centro del laberinto, que representa el hilo.

• Karel inicia en algún lugar del cuadrado exterior del laberinto sin una orientación específica.
• Karel NO inicia junto a una puerta.
• Karel lleva un número infinito de zumbadores en la mochila.
• El minotauro el cual siempre estará en el centro del laberinto, se representa como un montón de 1 zumbador.
• Para obtener puntos en este problema, Karel debe dejar el camino de zumbadores que se describe en la sección problema.
• No importa la posición ni la dirección final de Karel.

El lado izquierdo muestra a Karel en el cuadrado exterior y el minotauro en el centro. El lado derecho muestra el camino de montones de un zumbador que representa el hilo.

Se agradece al Comité Olímpico Mexicano de Informática el permiso para publicar este problema en nuestro sitio; que fue aplicado en el examen nacional de la 16a OMI, celebrada en la ciudad de Cuernavaca, Morelos en el año 2011.