Az Aknakereső egy ismert játék a 80-as évekből. A Microsoft Windows bizonyos verzióiban a mai napig előre telepítve van. A játék egy cellákból álló négyzetrácson zajlik. A cellák tartalma eredetileg el van rejtve. Összesen M cellában akna található (egy cellában legfeljebb egy akna lehet). A cellákra rákattinthatunk, hogy megismerjük tartalmukat. Ha olyan cellára kattintunk, amiben aknak van, vége a játéknak. Egyébként egy szám jelenik meg a cellában, ami 0 és 8 közé esik, és azt adja meg, hogy a választott cella nyolc szomszédjában összesen hány akna van. A szomszédság egy közös él vagy egy közös csúcs kell. Ha a felfedett cella 0 szomszédja tartalmaz aknát, akkor összes szomszédja is felfedetté válik, és ez rekurzív folytatódik a szomszédok szomszédaival. Ha az összes cella fel lett fedve, ami nem tartalmaz aknát, megnyertük a játékot. A következő példában egy játék kezdeti állapotát láthatjuk ('*' jelöli az aknát, 'c' az első kattintás helyét, '.' pedig az üres cellát): *..*...**. ....*..... ..c..*.... ........*. ..........Mivel az eredeti kattintás szomszédságában nincs akna, ő nulára lesz állítva, és a nyolc szomszédja is fel lesz fedve. A folyamat egészen addig folytatódik, amíg az alábbi állapothoz nem jutunk: *..*...**. 1112*..... 00012*.... 00001111*. 00000001..Mivel még vannak fel nem fedett cellák, újra kattintani kell a játék folytatásához. FeladatSzeretnénk a játékot gyorsan megnyerni, ezért szeretnénk tudni, hogy egy (R x C) méretű táblán el lehet-e helyezni úgy M aknát, hogy a tábla egyetlen kattintással megnyerhető legyen. Az első kattintás helyét megválaszthatjuk. Ha lehetséges, akkor írjunk ki egy megfelelő akna-konfigurációt, megjelölve az első kattintás helyét. Ha nem lehetséges, akkor az "Impossible" szöveget kell kiírni.
|
Programozás > Feladatok >
