- Esta compuesto por una malla rectangular de habitaciones, F filas por C columnas (R rows by C columns).
- 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.
- Existe exactamente una ruta entre dos habitaciones cualesquiera en el laberinto(esto es, exactamente una ruta que no involucre un retroceso).
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? |
|---|---|---|---|---|
| 1 | Sí | No | No | No |
| 2 | No | Sí | No | No |
| 3 | Sí | Sí | No | No |
| 4 | No | No | Sí | No |
| 5 | Sí | No | Sí | No |
| 6 | No | Sí | Sí | No |
| 7 | Sí | Sí | Sí | No |
| 8 | No | No | No | Sí |
| 9 | Sí | No | No | Sí |
| a | No | Sí | No | Sí |
| b | Sí | Sí | No | Sí |
| c | No | No | Sí | Sí |
| d | Sí | No | Sí | Sí |
| e | No | Sí | Sí | Sí |
| f | Sí | Sí | Sí | Sí |
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
