BACKGROUND
Muchas áreas de la Informática utilizan dominios simples y
abstractos para los estudios analíticos y empíricos. Por ejemplo, un estudio
inicial AI de la planificación y la robótica (tiras) utiliza un mundo de
bloques en el que un brazo de robot lleva a cabo las tareas que implican la
manipulación de bloques.
En este problema va a modelar un mundo simple bloque bajo
ciertas reglas y limitaciones. En lugar de determinar la forma de lograr un
estado especificado, debes programar un brazo robótico para responder a un
conjunto limitado de comandos.
EL PROBLEMA
El problema es analizar una serie de comandos que instruyen
a un brazo de robot en la forma de manipular bloques que se encuentran sobre
una mesa plana. Inicialmente hay n bloques en la mesa (numeradas de 0 a n-1)
con el bloque b_i adyacente para bloquear b_(i + 1) para todo 0<=i<n ,
como se muestra en el siguiente diagrama:
Los comandos válidos para el brazo robot que manipula
bloques son:
Poner A sobre de B “move a onto b”
donde a y b son números de bloque, poner “a” encima de “b” y regresar cualquier bloque que estubiese encima
superior de los bloques A y B a sus posiciones iniciales.
poner a encima b “move a over b”
donde “a” y “b” son números de bloque, poner “a” encima de
la pila de bloque de contención b, después de regresar de cualquier bloque que
se apilan en la parte superior del bloque “a” a sus posiciones iniciales.
colocar a sobre b “pile a onto b”
donde a y b son números de bloque, poner la pila “a” sobre “b”,
Todos los bloques en la parte superior del bloque B se mueven a sus posiciones
iniciales antes de adoptar pila lugar.
apilar a sobre b “pile a over b”
donde a y b son números de bloqueas, apilar la fila “a”
sobre la fila “b”. Los bloques apilados encima de un bloque conservan su orden
original cuando se mueven.
dejar
termina manipulaciones en el mundo de bloques.
Cualquier comando en el que “a” sea igual a “b” o “a” y “b” estean en la misma pila de bloques
es una orden ilegal. Todos los comandos ilegales deben ser ignorados y no deben
tener ningún efecto en la configuración de los bloques.
ENTRADA
La entrada comienza con un entero n en una línea por sí
mismo que representa el número de bloques en el mundo bloque. Usted puede
asumir que 0 <n <25.
El número de bloques es seguido por una secuencia de
comandos de bloque, un comando por línea. Su programa debe procesar todos los
comandos hasta que se encuentra el comando quit.
Usted puede asumir que todos los comandos serán de la forma
indicada anteriormente. No habrá comandos sintácticamente incorrectos.
SALIDA
La salida debe consistir en el estado final del mundo de los bloques. Cada posición debloque original numerado i (0<=i<n donde n es el número de bloques) debe aparecer seguido inmediatamente por dos puntos. Si hay al menos un bloque en él, los “:” deben ser seguido por un espacio, seguido por una lista de bloques que aparecen apilados en esa posición con cada número de bloque separado de otros números de bloque por un espacio. No ponga ningún espacio final de una línea.
Debe haber una línea de salida para cada posición del bloque (es decir, n líneas deproducción donde n es el número entero en la primera línea de la entrada).
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:
TRADUCIDO POR: Santiago
UVA: LINK UVA
No hay comentarios:
Publicar un comentario