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ť.