Programozás‎ > ‎Feladatok‎ > ‎

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

Bemenet  Kimenet
5 5 _#___ _#_#_ ___#_ _#Z#_ ##ZZ_12 1 1 2 1 3 1 3 2 3 3 4 3 5 3 5 4 5 5

Tesztadatok

Címkék

A feladat forrása: saját feladat
Algoritmusok: legrövidebb út keresése, szélességi bejárás

Aloldalak (1): Megoldás
ċ
zombik.zip
(10k)
Gábor Fehér,
2012. jún. 30. 5:46
Comments