II Copa MATCOM ACM-ICPCEnded |
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:
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.
EMPTY
Línea 1 … : El programa a ejecutar por Botty. Una instrucción por línea.
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++.