A megoldás
Betöltés, adatstruktúra
A térképet egy N-szer M-es karakter típusú tömbben fogjuk tárolni. A # falat fog jelölni, a Z egy zombit, a szóköz pedig átjárható mezőt. Most is célszerű lesz felvenni egy falakból álló keretet, hogy megkönnyítsük a tömbhatár-vizsgálatot.
Útkeresés
A 6.órán tanulthoz hasonló algoritmust fogunk írni. Az lesz a különbség, hogy itt nem csak azt tároljuk el egy mezőről, hogy elérhető-e a kiindulásból, hanem azt is, hogy mennyi idő alatt. (Kiindulásnak most az útvesztő jobb alsó sarkát fogjuk választani, és a feladat-kitűzésben szereplő iránynak pont a fordítottját fogjuk bejárni. Az útkeresés szempontjából ennek nincs jelentősége, de később majd hasznos lesz.)
Ehhez egy ido[sor, oszlop] tömböt fogunk használni, aminek kezdetben minden értéke maxIdo. maxIdo legalább egy legalább 1-gyel nagyobb szám, mint az útvesztőben lévő két mező közti lehetséges legnagyobb idő, és azt jelzi, hogy az adott mező elérhetetlen a kiindulási mezőből. Első körben csak a kiindulási mező ideje 0. (ido[n, M]:= 0) Ezután ismételgessük a következő lépést: Végignézünk sorban minden mezőt, és ha olyat találunk, ami már elérhető a kiindulási mezőből (ido[sor, oszlop] < maxIdo), akkor kiszámoljuk, hogy mennyi idő alatt lehet belőle eljutni a szomszédos mezőkbe. Ha valamelyik szomszédos mezőbe eredetileg még nem lehetett eljutni, vagy az adott mezőn keresztül rövidebb idő alatt el lehet bele jutni, akkor lecsökkentjük az idejét az ido[] tömbben, az újonnan kiszámolt értékre.
Mindezt addig ismételgetjük, amíg tudunk idő értéket változtatni. Tehát az első olyan lépés után fejezzük be, amiben már nem változott az ido[] tömb egy eleme sem.
Az legkülső feltételben a (ido[sor, oszlop] < maxIdo) kitétel elhagyható.
Ez az algoritmus csak az egyik szomszéd kezelését tartalmazza, a másik háromét még meg kell írni. Az algoritmus lefutása után a keresett idő, az ido[1, 1] helyen lesz megtalálható, de ebbe még nincs beleszámolva az [1, 1] (most a cél) mezőn való áthaladás ideje, azt hozzá kell adni!
Miért is működik ez?
Az állítás az, hogy az algoritmus lefutása után, amikor már egy mező idejét sem lehet csökkenteni (az ido[] tömbben), akkor minden mező ideje a kiindulásból a mezőbe érkezés lehető legrövidebb ideje lesz.
Az, hogy egy mezőre nem kerül ennél kisebb idő, könnyen végiggondolható. Azt pedig, hogy nagyobb sem kerülhet, indirekt módon fogjuk bizonyítani: tegyük fel, hogy az algoritmus már nem tud több mezőt csökkenteni, de még létezik néhány olyan mező, amibe rövidebb idő alatt is el lehet jutni, mint az ido[] tömbben hozzájuk felírt értékek.
Válasszuk ki ezen hibás idejű mezők közül azt, amelyik a valóságban a legrövidebb idő alatt érhető el a kiindulásból, és nevezzük mostantól X-nek! (Ha több ilyen van, akkor az egyiket. A lenti példában egy van: a 8-as idejű.) Tekintsük az ebbe a mezőbe vezető legrövidebb utat. (A példában zöld.) X-et kivéve ezen út mezőire már az algoritmus is helyes értékeket rakott. (Ha nem így lenne, akkor létezne a kiinduláshoz X-nél "időben közelebbi" hibás mező...) Most két lehetőség van: X ideje vagy annyi, amennyi idő alatt el lehet érni a legrövidebb úton, vagy nagyobb. Annyi nem lehet, mert az pont az a legkisebb idő, amennyi alatt a kiindulásból odaérünk, de X-nél tudjuk, hogy ennél nagyobb szerepel.
Ha nagyobb, akkor viszont az algoritmus csökkenteni tudja, amikor az úton lévő szomszédjához érkezik. (Példánkon ez a Z-betűs 5-ös.) Tehát nem lehet igaz az indirekt feltevésnek az a része, hogy már leállt az algoritmus. Így igaz kell, hogy legyen az eredeti állítás: minden mezőn a legkisebb elérési idő fog szerepelni, amikor már nem tud tovább csökkenteni az algoritmus. (Ilyen állapot pedig biztosan el fog érkezni.)
A piros Z-vel jelölt mezők zombik, a zöld a legrövidebb út. Az algoritmus a következő lépésben a 8-at 7-re cseréli, tehát valóban nem volt kész...
A legrövidebb út
Miután feltöltöttük az ido[] tömböt, már tudjuk a legrövidebb időt, de még nem tudunk mutatni egy legrövidebb utat hozzá. A cél mezőből kiindulva érdemes keresni egyet. Megnézzük, hogy az idők alapján melyik szomszédos mezőből érkezhettünk a célba, és vesszük azt a pl. Y mezőt. A következő lépésben azt kell megnézni, hogy Y-ba melyik szomszédjából érkezhettünk, és így tovább. Előbb utóbb el kell érnünk a kiindulási mezőt, mert mindig kisebb idejű mezőre lépünk. A bejárás közben minden így bejárt mező koordinátáit kiírjuk. (Ezért vettük a feladatkitűzésben szereplő cél mezőt az útkeresésben kiindulásnak, mert így helyes sorrendben kapjuk meg a koordinátákat, és nem pedig fordítottban.) A Lehete(sor, oszlop, sz_sor, sz_oszlop) eljárás eldönti, hogy a [sor, oszlop] koordinátájú mezőbe érkezhettünk-e az [sz_sor, sz_oszlop] koordinátájúból:
Ennek felhasználásával a visszakereső-függvény:
A ciklus akkor lép ki, amikor elérte a kiindulási mezőt, ami a feladatkitűzésben a cél volt.
Megoldások
- fg_zomb.pas (Fehér Gábor, Pascal)
- mb_zomb.c (Mészáros Balázs, C)
- tb_zomb.vb (Tihanyi Balázs, Visual Basic.NET)