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.
Eljárás UtKeres
ido[n, M]:= 0;
volt := Igaz;
Ciklus amíg volt = Igaz
volt:= Hamis;
Ciklus sor := 1-től N-ig
Ciklus oszlop:= 1-től M-ig
Ha (map[sor, oszlop] <> '#')
és (ido[sor, oszlop] < maxIdo) Akkor
ujido:= ido[sor, oszlop]+1;
Ha map[sor, oszlop] = 'Z' Akkor ujido:= ujido+1;
Ha (map[sor+1, oszlop] <> '#') és
(ujido < ido[sor+1, oszlop]) Akkor
ido[sor+1, oszlop]:= ujido;
volt:= Igaz;
Elágazás vége
Elágazás vége
Ciklus vége
Ciklus vége
Ciklus vége
Eljárás vége
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:
Eljárás Lehete(sor, oszlop, sz_sor, sz_oszlop)
Ha map[sz_sor, sz_oszlop] <> '#' Akkor
ido0:= ido[sz_sor, sz_oszlop]+1;
Ha map[sz_sor, sz_oszlop] = 'Z' Akkor
ido0:= ido0+1;
Lehete:= (ido0 = ido[sor, oszlop]);
Különben
Lehete:= Hamis;
Elágazás vége
Eljárás vége
Ennek felhasználásával a visszakereső-függvény:
Eljárás Visszakeres()
sor:= N; oszlop:= M;
Kiir(sor, ' ', oszlop);
Ciklus Amíg (táv[sor, oszlop] > 0)
Ha Lehete(sor, oszlop, sor+1, oszlop) Akkor
sor := sor + 1;
Különben Ha Lehete(sor, oszlop, sor-1, oszlop) Akkor
sor := sor - 1;
Különben Ha Lehete(sor, oszlop, sor, oszlop+1) Akkor
oszlop:= oszlop + 1;
Különben Ha Lehete(sor, oszlop, sor, oszlop-1) Akkor
oszlop:= oszlop - 1;
Elágazás Vége
Kiir(sor, ' ', oszlop);
Ciklus Vége
Eljárás Vége
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
