Feladat: S.27 Korcsoport: - Nehézségi fok: -
Füzet: 2007/május, 295 - 296. oldal  PDF file
Témakör(ök): Számítástechnika, informatika, Nehezebb feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Írjunk programot, amely a páros aknakereső játékban egy tetszőleges állásban lépést javasol.
A játék egy N×M-es táblán folyik, amelynek mezőin K db akna van elrejtve (egy mezőn legfeljebb csak egy). Kezdetben az összes mező felderítetlen. A játék során a két játékos felváltva választ egy-egy, még felderítetlen mezőt. Ha a kiválasztott mező aknát rejt, a játékos 1 pontot szerez, és újból választhat. Ellenkező esetben megtudjuk, hogy a kiválasztottal szomszédos 8 mező közül összesen hány rejt aknát ‐ ez egy 0 és 8 közötti egész szám ‐, és a másik játékos következik. Kivételt képez az az eset, amikor a játékos olyan (aknamentes) mezőt derít fel, amely körül egy akna sincs, ugyanis ekkor az összes szomszédos mező is felfedésre kerül, illetve ha így olyan mező kerül felfedésre, amely körül szintén nincs egy akna sem, az eljárás rekurzívan ismétlődik. Természetesen ezután ebben az esetben is a másik játékos következik.
A játék végeztével, azaz az összes akna megtalálása után, az nyer, akinek több pontja van.
A program az aktuális játékállást a standard bemenetről olvassa. A bemenet első sorában három egész szám szerepel: a tábla N szélessége és M magassága, továbbá az elrejtett aknák K száma, egy-egy szóközzel elválasztva. Az ezt követő M sor mindegyike N karaktert tartalmaz: a bemenet (i+1)-edik sorának j-edik karaktere a játéktábla i-edik sorának és j-edik oszlopának kereszteződésében lévő mezőt írja le. Ez

pont (.), ha a mező még federítetlen
csillag (*), ha a mezőt már felderítette valamelyik játékos, és aknát tartalmaz
0 és 8 közötti számjegy, ha a mező már felderített, de nem rejtett aknát (ekkor ez az érték a mező szomszédságában lévő aknák száma).

A program a javasolt lépést ‐ 10 másodpercen belül ‐ a standard kimenetre írja. Ennek egyetlen sorában két, szóközzel elválasztott egész szám szerepeljen: a felderítendő mező X oszlop- és Y sorindexe (1XN, 1YM).
A működőképes megoldások között körmérkőzést rendezünk. A programok 10‐20 játékból álló csoportokban mérik össze tudásukat, a csoport győztese az a program, amely a játékok legalább 2/3 részét nyeri. Ha ezt az arányt egyik program sem éri el, a csoport eredménye döntetlen. Mérkőzésenként a győztes 3 pontot kap, döntetlen esetén pedig mindkét játékos 1‐1-et. A megoldásokat az így kialakult pontszám alapján rangsoroljuk, az első helyezett (megfelelő dokumentáció esetén) 10 pontot, a második 8-at, a többi megoldás legfeljebb 7 pontot kaphat. Kis különbségek esetén az első, illetve második helyen több megoldás is végezhet.
Feltehetjük, hogy a program bemenetére kizárólag helyes játékállás érkezik, továbbá, hogy N,M100.
 
 

Beküldendő a program forráskódja (s27.pas, s27.cpp, ... és dokumentációja).