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 beepers 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 beepers por cada movimiento de la siguiente manera:

1 beeeper representa un movimiento hacia el oeste, 2 beepers un movimiento hacia el norte, y 3 beepers 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.

Ejemplo

Consideraciones

• Karel tiene infinitos beepers 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