03004 Karel y Gretel Reload
Problema 3 del Segundo Cuasiexamen Práctico de la V OIEG

Historia

Como era costumbre Gretel salió desde temprano (como a la 6 a.m.) al bosque en busca de beeperleñas. Un poco más tarde (por eso de las 10 a.m.) salio Karel con el mismo propósito. Conociendo a Karel, Gretel tiene la sana costumbre de dejar beepers por donde ha pasado. Para la mala suerte de Karel, una beeperave (un pájaro que come beepers) ha comido muchos beepers del camino aunque dejó los suficientes para que Karel pueda reconstruir el camino y encontrar a Gretel (era buena onda la beeperave).

El camino que dejo Gretel (antes que pasara la beeperave) esta hecho de manera que cada beeper está a sólo un paso del anterior y del siguiente (más no se sabe en que dirección) y no hay caminos que se cruzan. Además, no hay paredes sobre el camino y si se da un paso en la dirección equivocada, nunca habrá un beeper ahí. No hay pared a un paso del camino.

Problema

Debes encontrar un algoritmo para que Karel reconstruya el camino de beepers que dejo Gretel, es decir, debes rellenar de nuevo el camino donde falten beepers.

Consideraciones

• Inicialmente Karel se encuentra sobre el primer beeper.
• Las discontinuidades, en el camino de beepers, siempre están entre un par de beepers alineados del camino y no se sabe el largo de la discontinuidad.
• Karel topará con Pared si equivoca la dirección.
• Karel termina si se topa con pared antes de un beeper, en cualesquiera de las direcciones disponibles (sin contar de donde viene) que tiene.
• Karel debe terminar en el último beeper del camino con cualquier orientación.
• Karel tiene suficientes beepers para colocar. Al menos, los que requiere el camino.
• Karel está dando la espalda a un lugar donde no hay camino.

Documento PDF | Casos de Prueba * | Solución: Karel y Gretel Reload

* Incluye archivos de evaluación

Estadísticas de Visitas

Última actualización:
Por Marte Ramírez