Programozás‎ > ‎Feladatok‎ > ‎Zombik‎ > ‎

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 azido[] 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;
          Elágazás vége
          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;
    Elágazás vége
    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


Fehér Gábor (Pascal):  fg_zomb.pas
Mészáros Balázs (C): mb_zomb.c
Tihanyi Balázs (Visual Basic.NET) tb_zomb.vb
ċ
fg_zomb.pas
(3k)
Gábor Fehér,
2012. jún. 30. 6:32
ċ
mb_zomb.c
(2k)
Gábor Fehér,
2012. jún. 30. 6:33
ċ
tb_zomb.vb_
(2k)
Gábor Fehér,
2012. jún. 30. 6:33
Comments