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 |