NézetNyomtat

Fordulj mindig balra
Címkék > Feladat
Versenyek > Google Code Jam > 2009 > Qualification Round

Fordulj mindig balra

Egy tökéletes labirintus előtt állsz. Egy labirintus akkor "tökéletes", ha a következők teljesülnek:
  1. Téglalap rácsban elhelyezkedő szobákból áll, R sora és C oszlopa van.
  2. Pontosan két ajtó vezet ki a labirintusból : a bejárat és a kijárat. A bejárat mindig az északi falon van, a kijárat bárhol lehet.
  3. A labirintus bármely két szobája között pontosan egy út vezet (ha nem engedünk meg visszalépést).
A "fordulj mindig balra" algoritmussal akarsz átjutni a labirintuson, ami szerint a haladási lehetőségek közül mindig a "legbalrább" levőt választod. Zsákutcába érve kétszer jobbra fordulsz (vagyis 180 fokkal jobbra), majd tovább mész. (A bal kezeddel mindig fogod a falat.) Ha kiértél, még egyszer "megoldod" a labirintust, de most a kijárattól indulva.
Utad három karakterrel írható le: 'W': egyenes továbbmész a következő szobába, 'L': balra fordulsz 90 fokot, 'R': jobbra fordulsz 90 fokot. Mindig kintről indulsz, a (z északi) bejárat előtt, befelé nézve. Az útnak akkor van vége, ha kiléptél a labirintusból.
A következő labirintus így járható be WRWWLWWLWWLWLWRRWRWWWRWWRWLW, ha északról indulunk és nyugaton jövünk ki.
Ha nyugaton lépünk be, és északon ki, akkor így néz ki az út: WWRRWLWLWWLWWLWWRWWRWWLW.

Feladat

Ismerve két utadat a labirintuson át (bejárattól kijáratig, majd kijárattól bejáratig), határozd meg a labirintus teljes leírását.

Bemenet

Az input első sora a tesztesetek száma, N. N eset jön ezután. Mindegyik így néz ki:
bejárattól_kijáratig kijárattól_bejáratig
Minden út legalább két karakter, ezek közül: 'W'-előre (walk), 'L'-balra (left), és 'R'-jobbra (right), és minden út 'W'-vel kezdődik és végződik.

Kimenet

Minden tesztesethez kiírunk egy sort: "Case #x:" formában. Ezután R sorban a labirintus leírása következik. Minden sor C karakterből áll, ami a szobákat írják le, a következő táblázat szerint:
Karakter Mehetek északra? Mehetek délre? Mehetek nyugatra? Mehetek keletre?
1igennemnemnem
2nemigennemnem
3igenigennemnem
4nemnemigennem
5igennemigennem
6nemigenigennem
7igenigenigennem
8nemnemnemigen
9igennemnemigen
anemigennemigen
bigenigennemigen
cnemnemigenigen
digennemigenigen
enemigenigenigen
figenigenigenigen

Példa

atl.inatl.out
2
WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3

Méretek

1 ≤ N ≤ 100.

Kis bemenet

2 ≤ hossz(bejárattól_kijáratig) ≤ 100,
2 ≤ hossz(kijárattól_bejáratig) ≤ 100.

Nagy bemenet

2 ≤ hossz(bejárattól_kijáratig) ≤ 10000,
2 ≤ hossz(kijárattól_bejáratig) ≤ 10000.

Tesztadatok