Informatika gyűjtemény

Egy szinttel feljebb Megoldás

2004050607080910

NézetNyomtat

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