Matcom Online Grader

Botty es el robot de Fito que lo ha acompañado toda la vida. Botty es un robot no muy avanzado que tiene forma de esfera y es rojo. Adicionalmente cuenta con un set de instrucciones (API llamado TyBot ) de forma tal que cualquiera puede programarlo. Fito se ha propuesto crear un programa que le permita a Botty llegar desde una posición de un laberinto a otra (llamada meta). Esta tarea se le ha presentado muy difícil y te ha pedido ayuda. Dado el conjunto de instrucciones que puede realizar Botty, usted debe crear un programa en TyBot que conduzca al robot desde un punto a otro en un laberinto.

El laberinto está formado por una grilla de $R$ filas y $C$ columnas y divido en $R \times C$ celdas. Una celda puede estar vacía o tener un obstáculo (cubo unitario). El laberinto siempre está rodeado por una pared que impide a Botty ir más allá de los límites permitidos. La siguiente imagen muestra un laberinto de 17 filas por 8 columnas, Botty se encuentra en la posición $(2, 2)$ y debemos llevarlo hasta la posición $(14, 6)$. Cuando Fito pone a Botty en un laberinto lo hace de forma tal que este se encuentre “mirando” al norte.

Las instrucciones para Botty expuestas en TyBot son las siguientes:

• move : Mueve a Botty una unidad hacia donde está mirando. Si la celda de destino está bloqueada, Botty choca y se avería, el programa para de ejecutar.
• turn : Hace girar a Botty 90 grados hacia la izquierda (por el eje z ). Luego de hacer turn , si Botty estaba mirando al norte , quedaría mirando al oeste ; si estaba mirando al oeste , quedaría mirando al sur ; si estaba mirando al sur , quedaría mirando al este y si estaba mirando al este quedaría mirando al norte . En la imagen anterior Botty está mirando al norte.
• mark : Para cada laberinto, Fito le asigna a Botty  una memoria de R * C bits. Con esta instrucción, si Botty está en la posición (x, y) , donde (1 ≤ x ≤ R, 1 ≤ y ≤ C) entonces el bit ubicado en la posición x * (C - 1) + (y - 1) es puesto en 1. Si el bit tenia valor 1, entonces la operación no afectará dicho valor. Inicialmente todos los bits que constituyen la memoria de Botty son puestos en 0. Note que los bits correspondientes a los lugares bloqueados en el laberinto permanecerán con valor 0 durante todo momento, porque es imposible que Botty se encuentre en alguna posición bloqueada.
• marked : Verifica si el bit correspondiente a la casilla a la cual se movería Botty (con una operación move ) está con valor 1. Si es el caso, un bit llamado flag , se pondrá con valor 1, 0 en caso contrario. Note que flag es un bit adicional en la memoria de Botty que es puesto en 0 al inicio.
• done : Pone en 1 el bit flag si la casilla donde se encuentra Botty es la casilla de la meta, 0 en otro caso.
• blocked : Pone en 1 el bit flag si la casilla a la cual se movería Botty (con una operación move ) está bloqueada, 0 en caso contrario.
• label <name> : Establece una etiqueta con nombre <name> en la instrucción actual. <name> está compuesto por las 26 letras del alfabeto en ingles minúsculas y mayúsculas (‘a’, …, ‘z’, ‘A’, …, ‘Z’). Esta operación no provoca cambios en la memoria de Botty. No pueden existir dos etiquetas con el mismo nombre.
• ugoto <name> : Salto incondicional. El programa comienza a ejecutar a partir de la instrucción label <name> (Donde la etiqueta <name> fue definida). Si <name> no fue definida por alguna operación de tipo label , entonces el programa es inválido.
• cgoto <name> : Salto condicional. Igual que ugoto pero se produce un salto solo cuando el bit flag tiene valor 1. Luego de ejecutarse esta instrucción flag se pone en 0.
• exit : Termina la ejecución del programa. Si la posición de Botty después de finalizado el programa es igual a la posición de meta, entonces se dice que su programa ejecutó correctamente, en otro caso, incorrectamente.

Usted debe escribir un programa (en el lenguaje de su preferencia) que imprima a la salida estándar un programa en TyBot , tal que para un laberinto determinado, ubique a Botty en la celda final. Note que Botty no sabe nada sobre el laberinto, ni siquiera las dimensiones del mismo, solamente cuenta con las instrucciones especificadas anteriormente.

Este problema está dividido en tres sub-tareas:

Sub-tarea I

La meta siempre se encontrará adyacente a las paredes exteriores del laberinto, es decir, si la meta se encuentra en la posición (x, y) se cumple que x = 2 o y = 2 o x = R-1 o y = C-1. Adicionalmente, Botty estará ubicado en la posición (1, y) al inicio. ( Ver casos 0 y 1 ).

Sub-tarea II

El laberinto solamente estará bloqueado en las paredes exteriores, es decir, solamente habrán bloques en las posiciones (x, y) donde x = 1 o y = 1 o x = R o y = C. (Ver casos 2 y 3).

Sub-tarea III

Ni el laberinto, ni la posición inicial del robot y posición final cumplen propiedad alguna. (Ver casos 0, 1, 2, 3, 4, 5).

Notas

- 1 ≤ R ≤ 100, 1 ≤ C ≤ 100.

- Su programa ( TyBot ) no puede ejecutar más de 500000 instrucciones. La cantidad de instrucciones puede ser la que usted desee.

- Botty no puede chocar contra una pared, es decir, hacer move en dirección a una celda bloqueada.

- Note que su programa debe resolver el caso general, no un laberinto en específico. Usted puede enviar una solución diferente por cada sub-tarea y resolver las particularidades en dicha tarea.

- Siempre es posible llegar desde la posición inicial a la final.

Input

EMPTY

Output

Línea 1 … : El programa a ejecutar por Botty. Una instrucción por línea.

Sample test(s)

Hints

Hint

Para más información, descargue botty (Un IDE para TyBot) para probar sus programas. Dentro de dicho IDE existen 6 casos embebidos numerados 0, 1, …, 5. Los casos 0 y 1 corresponden a la sub-tarea I , los casos 2 y 3 a la sub-tarea II , y todos los casos pueden considerarse casos tipos de la sub-tarea III .

Programe en este IDE y cuando tenga la solución haga clic en Copy . Pegue la solución en la pestaña submit del jurado y luego envíe seleccionando el lenguaje C++.