Zombik
Ezt a feladatot órán kicsit másképpen tűztük ki, lásd a változás című bekezdést!
A feladat szövege
A gépterem számítógépei fellázadtak, mert folyton útvesztőket kellett csinálniuk. (Lásd:
6. óra,
7. óra
)
Büntetésül beraktak téged is egy útvesztőbe, és egyetlen esélyed, hogy megkeresed az egyik legrövidebb kivezető utat. (Ebben az útvesztőben több út is elvezet a kijárathoz.) Egy mezőn egy időegységbe kerül az áthaladás. A pályán vannak zombik is, de van nálad egy Rambo-kés, amivel egy időegység alatt le tudod őket győzni, tehát a zombit tartalmazó mezőkön két időegység az áthaladás.
Bemenet
A bementi fájl első sora a térkép sorainak N (1<=N<=101) számát és oszlopainak M (1<=M<=101) számát tartalmazza.
A következő N sor mindegyike M karaktert tartalmaz, melyek lehetnek szóközök, kettőskeresztekek, vagy Z betűk. A szóköz szabad utat jelöl, a kettőskereszt falat, a Z betű zombit. (Zombi természetesen minden mezőn lehet, a kiindulásin és a célon is...) Az útvesztő szélein lévő falak nincsenek jelölve.
Kimenet
A kimeneti fájl első sora legyen a bal felső sarokból a jobb alsó sarokba eljutás lehető legrövidebb ideje, melybe beleszámít az első és az utolsó mezőn áthaladás ideje is. A további sorok pedig tartalmazzák az egyik tetszőleges legrövidebb út mezőinek a koordinátáit.
Változás
Az órai változatban az első mező nem számított bele a megtett útba, itt viszont beleszámít!
Példa
Az _ (aláhúzás) jelek szóközöket jelölnek.
| PELDA.BE | PELDA.KI |
| 5 5
_#___
_#_#_
___#_
_#Z#_
##ZZ_ | 12
1 1
2 1
3 1
3 2
3 3
4 3
5 3
5 4
5 5 |
Tesztadatok
