Fordulj mindig balra
Egy tökéletes labirintus előtt állsz.
Egy labirintus akkor "tökéletes", ha a következők teljesülnek:
- Téglalap rácsban elhelyezkedő szobákból áll, R sora és C oszlopa van.
- 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.
- 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? |
| 1 | igen | nem | nem | nem |
| 2 | nem | igen | nem | nem |
| 3 | igen | igen | nem | nem |
| 4 | nem | nem | igen | nem |
| 5 | igen | nem | igen | nem |
| 6 | nem | igen | igen | nem |
| 7 | igen | igen | igen | nem |
| 8 | nem | nem | nem | igen |
| 9 | igen | nem | nem | igen |
| a | nem | igen | nem | igen |
| b | igen | igen | nem | igen |
| c | nem | nem | igen | igen |
| d | igen | nem | igen | igen |
| e | nem | igen | igen | igen |
| f | igen | igen | igen | igen |
Példa
| atl.in | atl.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
