Zadanie

V Slovakistane sa rozhodli osadníci usporiadať národný šachový turnaj. Za prvé miesto sa dá získať diplom, a tak všetci hrajú ako o život. Keďže sa však nehrá na čas, vyskytol sa problém – hráči nechceli priznať prehru. Stále len tvrdili, že určite nemajú mat, však určite sa z tej situácie dá nejak dostať, keby len mali ešte chvíľku na rozmýšlanie… A možno ešte jednu…

Na budúci rok sa bude TMŠ v Slovakistane organizovať zas, ale je potrebné tento problém dovtedy nejako vyriešiť.

Úloha

Pre daný popis šachovnice rozlíšte, či má niektorý z hráčov šach alebo mat. Pritom berte do úvahy len obyčajné pohyby figúrok (komplikované ťahy ako rošáda, en passant, pohyb pešiakom o dva políčka vpred a povýšenie pešiaka sa v Slovakistane neakceptujú).

Formát vstupu

V prvom riadku je číslo \(1 \leq t \leq 1000\), udávajúce počet šachovníc na vstupe. Nasleduje \(t\) popisov šachovníc.

Každý popis šachovnice pozostáva z ôsmich riadkov, každý obsahujúci osem znakov (teda šachovnica má klasické rozmery \(8 \times 8\)). Tieto znaky sú .KQRBHP, reprezentujúce v tomto poradí voľné políčko, kráľa, kráľovnú, vežu, strelca, koňa, a pešiaka.

Bielemu hráčovi patrí horná strana šachovnice (skôr na vstupe) a jeho figúrky sú označené malými písmenami. Teda bieli pešiaci sa pohybujú smerom dole. Čiernemu hráčovi patrí dolná strana šachovnice a jeho figúrky sú označené veľkými písmenami. Jeho pešiaci sa pohybujú smerom hore. Za každým popisom šachovnice je jeden prázdny riadok.

Počet ani poloha figúrok nijak nemusia byť dosiahnuteľné v klasickej hre šachu, avšak môžete predpokladať, že na každej šachovnici sa nachádza práve jeden biely kráľ (k) a práve jeden čierny kráľ (K).

Navyše, figúrky sa vo vstupoch budú vyskytovať nasledovne:

Číslo sady Nové figúrky
\(1\) Kráľ, kôň
\(2\) Veža
\(3\) Strelec, kráľovná
\(4\) Pešiak

Formát výstupu

Pre každú šachovnicu vypíšte jeden riadok s jednou z nasledovných hlášok:

  • “Neutralna situacia.”, ak žiaden z kráľov nie je ohrozený nepriateľskou figúrkou.

  • “Nemozna situacia.”, ak sú obaja králi ohrození nepriateľskou figúrkou.

  • “{farba} hrac ma sach.”, kde {farba} je “Biely”, resp. “Cierny”, ak je kráľ tohto hráča v ohrození, ale existuje platný ťah niektorou z jeho figúrok taký, po ktorom už v ohrození nebude.

  • “{farba} hrac ma mat.”, kde {farba} je “Biely”, resp. “Cierny”, ak je kráľ tohto hráča v ohrození, a neexistuje platný ťah niektorou z jeho figúrok taký, po ktorom už v ohrození nebude.

Príklady

Input:

3
....k...
........
...H....
........
...h....
........
....K...
........

........
....h...
..k.....
.....H..
...K....
........
........
........

k..H....
...H....
.HH.....
........
........
......K.
........
........

Output:

Nemozna situacia.
Neutralna situacia.
Biely hrac ma mat.

Všetky tri šachovnice by sa mohli vyskytnúť už v prvej sade.

Input:

4
k..H....
...H....
.HH.....
........
........
......K.
.r......
........

K.....Rr
R.h....r
........
........
rr......
.....k..
........
........

k.......
.......R
........
...B....
.R......
......K.
..q.....
........

........
..PPP...
..PkP...
...Pp...
...K....
........
........
........

Output:

Biely hrac ma sach.
Cierny hrac ma mat.
Biely hrac ma sach.
Cierny hrac ma sach.

Šachovnice v príklade by mohli byť najskôr v sadách 2,2,3,4.

Táto úloha bola trochu neklasická v tom, že jej obtiažnosť nespočívala vo vymyslení riešenia, ale jeho implementácií. Vzorák sa totiž prakticky nachádzal v samotnom zadaní:

“{farba} hrac ma sach.”, kde {farba} je “Biely”, resp. “Cierny”, ak je kráľ tohto hráča v ohrození, ale existuje platný ťah niektorou z jeho figúrok taký, po ktorom už v ohrození nebude.

Ak zistíme, že práve jeden kráľ je v ohrození, stačí nám vyskúšať každý ťah tohto hráča, a zakaždým sa spýtať znovu tú istú otázku – je kráľ v ohrození? Ak je aspoň raz odpoveď “nie”, odpovedáme šach, inak mat.

Vzhľadom na to že hlavným cieľom úlohy je donútiť riešiteľa si dopredu premyslieť ako túto jednu vetu naprogramovať čo najprehľadnejšie a bezbolestnejšie, hlavným cieľom vzoráku bude priblížiť ako k takémuto problému pristupovať, namiesto toho aby sa po vyslovení jednovetového riešenia prilepili strany hotového kódu.

Vzorové riešenie by teda, po prepísaní do pseudokódu, vyzeralo zatiaľ zhruba takto

string vyries()
{
    nacitaj a spracuj vstup

    B = je_ohrozeny(biely_kral,sachovnica)
    C = je_ohrozeny(cierny_kral,sachovnica)

    if B and C:
        return "Nemozna situacia."
    if !B and !C:
        return "Neutralna situacia."

    for priatelska_figurka in sachovnica:
        for nova_sachovnica in skus_vsetky_tahy(priatelska_figurka,sachovnica):
            if !je_ohrozeny(ohrozeny kral,nova_sachovnica):
                return farba + " hrac ma sach."

    return farba + " hrac ma mat."
}

main()
{
    t = input()
    while(t--)
        print(vyries())
}

Samozrejme vynechávam detaily ako načítanie vstupu a zapamätanie si pozícíí králov a pod. Štruktúra je tá dôležitá časť. Toto riešenie by teda bolo kompletné, ak by boli hotové funkcie je_ohrozeny(kto,kde) , ktorá zistí či figúrka kto na šachovnici kde je ohrozená nepriateľskými figúrkami, a skus_vsetky_tahy(kto,kde) ktorá zoberie figúrku kto a šachovnicu kde, a vygeneruje všetky možné šachovnice ktoré vzniknú tým, že touto figúrkou spravíme jeden ťah.

A teraz sa zamyslite, či sú si tieto funkcie navzájom podobné. Čo to vlastne znamená, že figúrka je v ohrození? No predsa to, že nejaká nepriateľská figúrka má taký ťah, ktorým sa posunie na pozíciu našej figúrky. Inak povedané, na overenie ohrozenosti vlastne chceme vyskúšať všetky ťahy nepriateľských figúrok. je_ohrozeny(kto,kde) teda, opäť odhliadnuc od detailov, vyzerá takto

bool je_ohrozeny(kto,kde)
{
    for nepriatel in nepriatelske_figurky:
        for nova_sachovnica in skus_vsetky_tahy(nepriatel,kde):
            if nova_sachovnica[pozicia kto] == nepriatel:
                return true
    return false
}

Ostáva nám teda už len skus_vsetky_tahy. Máme vlastne dva typy figúrok: tie ktoré majú určitý počet pohybov (kôň a kráľ) a tie ktoré maju určitý počet smerov, v ktorých môžu ísť kým nenarazia na prekážku (okraj šachovnice alebo figúrku). Môžeme teda napríklad zostrojiť dve funkcie, jedna ktorá vyskúša dané pohyby (a použijeme ju pre kráľa a kone), a jednu ktorá vyskúša pohyby v daných smeroch. Pešiakov bude jednoduchšie naprogramovať osobitne. Celé to môže vyzerať zhruba nasledovne

sachovnica[] niekolko_pohybov(figurka kto,sachovnica kde)
{
    sachovnica[] results

    for pohyb in kto.pohyby:
        if mozem(kto.pozicia + pohyb):
            tmp = kde[kto.pozicia + pohyb]
            kde[kto.pozicia] = '.'
            kde[kto.pozicia + pohyb] = kto
            results.append(kde)
            kde[kto.pozicia] = kto
            kde[kto.pozicia+pohyb] = tmp

    return results
}

sachovnica[] pohyb_v_smere(figurka kto,sachovnica kde)
{
    sachovnica[] results

    for smer in kto.pohyby:
        pohyb = smer
        while mozem(kto.pozicia+pohyb):
            tmp = kde[kto.pozicia + pohyb]
            kde[kto.pozicia] = '.'
            kde[kto.pozicia + pohyb] = kto
            results.append(kde)
            kde[kto.pozicia] = kto
            kde[kto.pozicia+pohyb] = tmp
            pohyb += smer

    return results
}

sachovnica[] skus_vsetky_pohyby(figurka kto, sachovnica kde)
{
    if kto == pesiak:
        //riešiť samostatne (zvoliť správny smer podľa farby, útočiť šikmo...)

    if kto == kral or kto == kon:
        return niekolko_pohybov(kto,kde)

    return pohyb_v_smere(kto,kde)

}

Pritom mozem(pozicia) vráti true ak je naša figúrka povolená pohnúť sa na dané políčko (teda nie je mimo šachovnice a nie je na nej priateľská figúrka). Tú tu uvádzať hádam nemusím.

Toto je teda kompletná štruktúra riešenia. Samozrejme, ešte chýba kopa práce utlačiť syntaktické detaily – napríklad pozicia by asi mala byť dvojica súradníc, každej figúrke musíme priradiť množinu pohybov vo forme dvojíc {dx,dy}, čo a ako si pamätáme o šachovnici, a tak ďalej, skúsenejším by však táto časť už nemala robiť veľké problémy.

Ak by ste si mali z tejto úlohy niečo odniesť, tak je to to, že riešenie úlohy nie vždy končí vymyslením algoritmu, naopak, niekedy to len začína. Vtedy je dobré si všetko pomaly dopredu premyslieť – chvíľkou rozvážneho plánovania štruktúry vášho programo si často môžete ušetriť hodiny programovania a najmä debugovania, jednoduchej myšlienky komplikovaným či zdĺhavým spôsobom.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.