Habitantes: 31962
11 invitados en línea.
Karelotitlán OMI OMI-DF
Página principal R e g í s t r a t e Problemas Karel Usuarios

   Bienvenido(a) invitado(a)
Iniciar sesión

El maléfico Chuzpa

11a OMI, San Luis Potosí 2006

Descripción

En esta 11° OMI Karel se encuentra en peligro, ya que ha sido blanco de los ataques del maléfico Chuzpa, para sobrevivir, al menos durante este problema, Karel debe huir a través de un campo de zumbadores avanzando desde la pared sur del campo hasta la pared norte, si Karel alcanza la pared norte quedará salvado.

A partir de su segunda fila (contando de sur a norte), el campo se encuentra salpicado de zumbadores que representan maleficios. Karel puede huir utilizando únicamente aquellos espacios en donde no hay maleficio.

Problema

Dado un campo rectangular, rodeado en su totalidad por paredes, encuentra la secuencia de movimientos que Karel necesita realizar para alcanzar la pared norte del campo. Tu programa deberá escribir la secuencia de movimientos en la primera fila del campo, dejando un montón de zumbadores por cada movimiento de la siguiente manera:

1 zumbador representa un movimiento hacia el oeste, 2 zumbadores un movimiento hacia el norte, y 3 zumbadores un movimiento hacia el este. La secuencia de movimientos deberá comenzar en la coordenada (1,1) y continuar sin dejar ningún espacio en blanco.

Consideraciones

  • Karel tiene infinitos zumbadores en la mochila
  • Karel se encuentra en cualquier lugar de la fila 1 orientado hacia el norte
  • Para los casos de prueba siempre habrá una forma de alcanzar la pared norte.
  • Karel es inteligente y sabe que es inútil pasar dos veces por el mismo lugar.
  • Si hay más de una forma (que cumpla con la consideración anterior), cualquiera que describas será considerada correcta.
  • No importan la orientación ni la posición final de Karel.
  • Los movimientos al sur no están permitidos.
  • Todos los casos de prueba tendrán al menos una solución cuya secuencia de pasos sea menor o igual a la longitud de la primera fila.

Ejemplo

Imagen

Mundo de ejemplo

Imagen

Solución al mundo de ejemplo

Agradecimiento

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 11a OMI, celebrada en la ciudad de San Luis Potosí, San Luis Potosí en el año 2005.




Envio de archivos para evaluación
Para enviar una solución a este
problema, por favor inicia sesión.

Karelotitlán v1.2.6
por Félix Rafael Horta Cuadrilla
Créditos

Karelotitlán funciona mejor en Mozilla Firefox y Google Chrome ¡Pruébalos!