Fuvarozás
Stanford Local Programming Contest, 2008, 3. feladat
A GPS jó dolog, de nem mindenható. Nem tudja például figyelembe venni a közlekedési lámpák pillanatnyi állását. Ha a leggyorsabban szeretnénk egy A pontból egy B pontba jutni, akkor lehet, hogy ezt is figyelembe kell vennünk. (Az A raktárból a B raktárba kell teherautóval árut szállítanunk.)
"Városunkat" a következő módon fogjuk kódolni:
#A##0##1#
.#..#..#.
.#..#..#.
.###2#.B.
.#..#..#.
.#..#..#.
.###2#.B.
A térkép
A térképen 4 irányba lehet lépni (fel, le, jobbra, balra), a kódok jelentése pedig a következő:
- #: út, ezen lehet haladni. Minden út szomszédos legalább két másik úttal, vagy kereszteződéssel vagy raktárral.
- 0-9: lámpás kereszteződés. Legalább három út szomszédos vele. Legfeljebb 10 van, 0-tól 9-ig számozva, egy szám csak akkor szerepel, ha az összes kisebb is előfordult. A lámpák működését később részletezzük.
- A: Innen indulunk.
- B: Ide kell eljutni.
- .: Fű, nem szabad ráhajtani.
A teherautó mozgása
Az időt egységekben (lépésekben) mérjük. Egy lépésben a teherautó léphet szomszédos útszakaszra (#), kereszteződésre (0-9), raktárra (A, B), vagy helyben is maradhat.
Kereszteződésre csak akkor léphetünk, ha abban az irányban zöld a lámpa, ahonnan rá akarunk lépni. Ha viszont már ráléptünk a mezőre, akkor bármerre léphetünk róla, bármelyik időpontban.
A lámpák
A lámpáknak van egy kezdeti állása ('-' = kelet-nyugat vagy '|' = észak-dél) és periodikusan váltanak, mindig x időt kelet-nyugat majd y időt észak-dél irányban jeleznek zöldet.
Például a kezdetben '|' állapotú és a "2 3" számpárral leírt lámpa állapotai időegységenként:
1: |
2: |
3: |
4: -
5: -
6: |
7: |
8: |
9: -
stb...
2: |
3: |
4: -
5: -
6: |
7: |
8: |
9: -
stb...
Feladat
Írj programot, ami kiszámolja, legkevesebb hány időegység eljutni A-ból B-be!
Bemenet
Több teszteset van egy állományban, mindegyik egy térképet és a lámpák működését adja meg.
A térkép mérete m sor és n oszlop, mindkettő 1 és 20 közé esik. A térkép a fent leírt módon van kódolva. A lámpákat sorszámukkal, kezdeti állapotukkal és x y értékeikkel adjuk meg. x és y a kelet-nyugati és észak-déli "nyitva tartás" időtartama, mindkettő 1 és 100 közötti egész. Az eseteket üres sor választja el, és a "0 0" sor zárja.
Kimenet
Minden tesztesethez adjuk meg a leggyorsabb út időtartamát, vagy az "impossible" szöveget, ha nincs út A-ból B-be-
Példa
| cargo.in | cargo.out |
3 4 A##B #..# #### 4 9 #A##0##1# .#..#..#. .#..#..#. .###2#.B. 0 - 1 17 1 | 3 5 2 - 2 4 2 2 A. .B 0 0 |
3 17 impossible |