NézetNyomtat

Fuvarozás
Címkék > Feladat

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.

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...

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.incargo.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

Tesztadatok