28 jun 2008

Un laberinto

Te encuentras parado afuera de un laberinto perfecto. Un laberinto se denomina "perfecto" si cumple las siguientes condiciones:
  1. Esta compuesto por una malla rectangular de habitaciones, F filas por C columnas (R rows by C columns).
  2. Tiene exactamente dos salidas hacia fuera del laberinto: la entrada y la salida. La entrada esta siempre en la pared norte, mientras que la salida puede estar en cualquier pared.
  3. Existe exactamente una ruta entre dos habitaciones cualesquiera en el laberinto(esto es, exactamente una ruta que no involucre un retroceso).
Has decidido resolver el laberinto perfecto utilizando el algoritmo "voltear siempre a la izquierda", que indica que debes tomar la desviación más a la izquierda en cada oportunidad. Si encuentras una ruta sin salida, volteas dos veces (180 grados en el sentido horario) y continuas. (Si sacas la mano izquierda y tocas la pared mientras sigues este algoritmo, resolveras el laberinto sin siquiera perder contacto con la pared). Cuando has terminado el laberinto, decides realizar un paso adicional y resolverlo nuevamente (siempre volteando a la derecha), pero empezando desde la salida y terminando en la entrada.

La ruta que tomas a través del laberinto puede ser descrita con tres caracteres: 'W' significa caminar hacia delante hacia la siguiente habitación, 'L' significa voltear 90 grados a la izquierda (o en sentido antihorario), y 'R' significa voltear 90 grados a la derecha (o en sentido horario).

Inicias directamente fuera de la entrada, de frente al laberinto. Finalizas cuando has salido fuera del laberinto a través de la salida.


Problema

Por ejemplo si la entrada esta en el norte y la salida en el oeste, tu ruta de salida a través del laberinto mostrado sería

WRWWLWWLWWLWLWRRWRWWWRWWRWLW

Si la entrada y la salida fueran invertidas, de modo tal que iniciaras fuera de la pared este y finalizaras fuera de la pared norte, tu ruta sería:

WWRRWLWLWWLWWLWWRWWRWWLW

Dadas lass dos rutas a través del laberinto (entrada hacia salida y salida hacia entrada), tu código debe retornar una descripción del laberinto.

Entrada

La primera línea de la entrada provee el número de casos, N. Siguen los N casos de prueba. Cada caso es una línea con el formato:

entrada_a_salida salida_a_entrada

Todas las rutas tendrán al menos dos caracteres de largo, compuestas solamente por los caracteres 'W', 'L', y 'R', y empezando y finalizando en 'W'.

Salida

Para cada caso de prueba, la salida debe mostrar una línea "Case #x:" por sí misma. Las siguientes F lineas (R lines) otorgan una descripción del laberinto F x C (R by C).
Cada línea debe tener C caracteres, cada uno representa las direcciones en las cuales es posible acceder a esa habitación. Vea la siguiente leyenda:
Caracter Norte? Sur? Oeste? Este?
1NoNoNo
2NoNoNo
3NoNo
4NoNoNo
5NoNo
6NoNo
7No
8NoNoNo
9NoNo
aNoNo
bNo
cNoNo
dNo
eNo
f



Limites

1 ≤ N ≤ 100.

Conjunto de datos pequeño

2 ≤ longitud(entrada_a_salida) ≤ 100,
2 ≤ longitud(salida_a_entrada) ≤ 100.

Conjunto de datos grande

2 ≤ longitud(entrada_a_salida) ≤ 10000,
2 ≤ longitud(salida_a_entrada) ≤ 10000.

Ejemplo

Entrada
2
WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW

Salida
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3

1 comentario:

Joseka dijo...
Este comentario ha sido eliminado por un administrador del blog.