Tulajdonképpen egy egyszerűsített
dijkstra-t kell alkalmaznunk (annyi különbséggel, hogy itt nem súlyokról beszélünk, legalábbis ha távolság alatt gyöngyöt értünk, akkor azt maximalizálni akarjuk). Van egy sorunk, ahol tároljuk a bejárandó csúcsokat (csúcs = jelen esetben egy mező). Betesszük a sorba
$(0,0)$-t, hiszen vele kezdünk. Innentől kezdve a következő az algoritmus:
- Kivesszünk a sorból egy mezőt. Amennyiben ő már jó mező, tehát biztosan maximális az odáig gyűjthető gyöngyök száma, akkor rögtön lépünk tovább a sorban a következő mezőre. Ha nem, akkor megjelöljük, hogy jó, hiszen a sorban előtte lévő mezők befolyásolhatták csak őt, melyek már megtették hatásukat.
- Ezután meglátogatjuk a "szomszédokat": tehát a tőle jobbra, illetve alatta lévő mezőket. Amennyiben lehet oda lépni (nem csapda) és érdemes is, tehát az odalépéssel legalább annyi gyöngyünk van, mint egy máshonnan ugyanide vezető úton, akkor rálépünk, azaz betesszük őt is a sorba.
- Közben minden egyes lépésnél megjegyezzük, hogy az adott mezőre melyik mezőről jutottunk el.
- Ha az algoritmus lefutott, akkor nyílván $(N, M)$ mező tartalmazza, hogy max. hány gyöngyöt tudtunk gyűjteni a játék során, az apa-pointerek pedig visszamutatnak az előző mezőkre, tehát az út is könnyen visszakövethető.
Főoldal
>
Versenyek
>
Nemes Tihamér OKSzTV
>
2007
>
Második forduló
>
11-13. osztály
>
Játék
>
Megoldás
