S.54.
Éles András, 12. évf
Debrecen, Fazekas Mihály Gimnázium
Ford.: Bloodshed Dev-C++ 4.9.9.2

A szokásos beolvasás után létrehozzuk a "szakaszokat". Egy szakasz egy sor vagy oszlop, melyben ismertek az összefüggő blokkok. Ezután minden szakaszt kielemzünk, megnézzük minden blokkjának lehető legkorábbi és legkésőbbi helyzetét. Erre a következő algoritmust használjuk: először berakjuk a blokkokat sorrendben mindet a lehető legelőbbre. Ezután fordított sorrendben minden blokk után megnézzük, van-e lefedendő mező (ami biztosan "X") ha igen, az adott blokkot előrébb kell elhelyezni. Így néhány blokk előrébb csúszott, erősebb becslésünk van a minimális kezdetre. Újra elvégezzük az algoritmust, de most már figyelembe véve az eddigi minimumot. És így tovább, amíg íly módon erősödik a lehetséges legkorábbi kezdet, legalább egy blokkra. Ugyanígy a legkésőbbi végződés is megkereshető blokkonként.

Ha egy blokk legkorábbi lerakása esetén a vége az X., legkésőbbi lerakása esetén az eleje az Y. mező, akkor Y<=A<=X esetén A biztosan 'X'. Nyilván a minimumok és maximumok sora monoton növő, így ha az egyik blokk maximuma és a rákövetkező minimuma közt van hézag, az '.'-tal kitölthető. Ugyanígy a legelső blokk minimuma előtt és az utolsó maximuma után is csak '.' lehet.

Az elemzést minden szakaszra elvégezzük, ahol van változás a korábbi állapotához képest, a jelöléseket végig jegyezzük. Ha elakadunk (elfogy a feldolgozandó szakasz, nincs változás), akkor tippelünk egy 'X'-et, és megjegyezzük. Ha ezután ellentmondásra jutunk, visszatérünk ehhez a helyzethez, és garantált a '.' az 'X' helyett. Nyilván több tippelés is kellhet egymás után. Íly módon a program megad egy megoldást, ha van.

typedef struct { short allapot; short ind[2][SMAX+1], veg[2][SMAX+1]; short sz1, sz2; } MEZO;
  MEZO t[SMAX*SMAX+1];
  SZAKASZ d[SMAX*SMAX+1];
  short varolista[2*SMAX*SMAX*SMAX+1], V1, V2;

A mezők O-s maradéka a j oszlopindex, O-s hányadosa az i sorindex ezután (sorsz=i*O+j)
allapot: 1 ha biztosan 'X', -1 ha biztosan '.', 0 ha nem tudjuk.
ind[2][SMAX+1] vízszintesen [0] illetve függőlegesen [1] indulhat-e adott hosszú blokk az adott mezőből (pontosan hány akadályozó tényező van. 0 esetén igen, különben nem). A szakaszelemzés megkönnyítésére szolgál. Folyamatosan módosítjuk, ha megjelölünk egy négyzetet.
sz1, sz2 a függőleges és vízszintes szakasz sorszáma.

typedef struct { short mez[SMAX+1], H; short blo[SMAX+1], B; bool vszintes, varolistan; } SZAKASZ;
  SZAKASZ d[SMAX*SMAX+1];
  short varolista[2*SMAX*SMAX*SMAX+1], V1, V2;

Egy szakasznak van H hossza (O vagy S), mezői mez[] tömbje, blokkjai hosszának blo[] tömbje és blokkjai B száma. vszintes jelöli, hogy sor vagy oszlop, varolistan pedig, hogy történt-e változás benne (fenn van-e a várólistán. Ha igen, felesleges újra feltenni.) varolista[] tárolja a feldolgozandó szakaszokat, V1 az elsőt, V2 az utolsót, ami elbírálásra fog kerülni (tapasztalat mutatta nálam, hogy a régebben meghívott szakasszal érdemesebb kezdeni, ezért mondjuk nem mindig a legutolsó berakott szakaszt bíráljuk el).

void Jelol (bool, short);
void Jeloles_visszavon (void);

Második argumentuma a szóban forgó mező, első pedig igaz, ha 'X', különben '.' Jelöli a mezőt a lépéslistában. A két érintett szakasz megváltozott, így várólistába teszi, ha kell. Legfontosabb, vezeti a ind[2][SMAX+1] és veg[2][SMAX+1] tömböket a mezőkre, így az akadályokat jegyzi (ha 'X', akkor akadály minden, a szomszédjában végződő blokkra, ha '.', akkor minden rajta átmenőre).
A másik függvény ezzel ellentétes művelet, visszavonja az utolsó lépést, tökéletesen visszatérve az időben (ellentmondásra jutáskor visszajutunk a legutóbbi jó helyzetbe).

bool Szakaszelemzes (short, short[], short[]);
  short huz_min[(SMAX+1)/2], huz_max[(SMAX+1)/2];

A szakaszelemzés a megoldás lelke. huz_min[] és huz_max[] lesz a szakasz blokkjainak lehető legkorábbi és legkésőbbi mezője.

short Tippelve_Jelol (void);

Tippel egy ismeretlen mezőt.

short lepeslista [SMAX*SMAX+1], L;
short allaspoz[SMAX*SMAX+1], A;

Ez az említett lépéslista, allaspoz[] pedig a tippelt lépések listája. Jelzi, meddig kell visszamenni ellentmondás esetén.

A programban a nagybetűk mindig tömbszámlálókat jelölnek, természetesen O-t és S-et kivéve, melyek jelentése értelemszerű. A tömbök mérete ővatos becslésekből következik - elég nagy mind.

int main() ezeket foglalja össze. A főciklus elkezdi elemezni a szakaszokat, amíg lehet (nem üres a várólisra, tehát van megváltozott, de nem újraelemzett szakasz). Ha elakadunk, akkor tippelünk, ezáltal keletkezik két új változás, és megyünk tovább. Ha ellentmondásra jutunk, visszatérünk a legutóbbi mentési pontig, és a másik ('.') alternatívát választjuk. Mivel a legvégén úgyis minden megváltozott szakaszra sor kerül, akkor is, ha az egész tábla már ki van töltve, a végső megoldás minden szakaszra nézve kielégítő lesz: tehát egy jó megoldást ad a program válaszul.