4. Turnaj Veľkých Šachistov vzorové riešenie

3
8 4
5 1 k
4 3 H
4 5 h
5 7 K

8 4
5 2 h
3 3 k
6 4 H
4 5 K

8 6
1 1 k
4 1 H
4 2 H
2 3 H
3 3 H
7 6 K

Nemozna situacia.
Neutralna situacia.
Biely hrac ma mat.

4
8 7
1 1 k
4 1 H
4 2 H
2 3 H
3 3 H
7 6 K
2 7 r

8 9
1 1 K
7 1 R
8 1 r
1 2 R
3 2 h
8 2 r
1 5 r
2 5 r
6 6 k

8 6
1 1 k
8 2 R
4 4 B
2 5 R
7 6 K
3 7 q

8 9
3 2 P
4 2 P
5 2 P
3 3 P
4 3 k
5 3 P
4 4 P
5 4 p
4 5 K

Biely hrac ma sach. Ma 1 platnych tahov.
Cierny hrac ma mat.
Biely hrac ma sach. Ma 1 platnych tahov.
Cierny hrac ma sach. Ma 5 platnych tahov.

Pred čítaním vzorového riešenia tejto úlohy si určite prečítajte aj vzorák jej ľahšej verzie z minulej série.

Táto úloha, rovnako ako jej predchodca, sa vyznačuje obtiažnosťou implementovať riešenie v kontraste s jeho samotným vymyslením; berie však túto úvahu trocha ďalej. Zatiaľ čo v Turnaji Mladých Šachistov nám malé šachovnice dovolili naprogramovať prakticky bruteforce typu “skúšaj všetky možné ťahy” a na nás bolo len rozvážne sa týmto skúšaním prehrýzť, v tejto úlohe bolo potrebné dávať si pozor, aby riešenie, s ktorým prichádzame, bolo zvládnuteľné. Ľahko sa totiž môže stať, že vymyslíme riešenie, ktoré je síce dosť rýchle, ale naloží nám oveľa viac roboty, ako by malo. Čím viac častí nášho riešenia používalo rovnaký kód, čím bol principiálne totožnejší s riešením predošlej úlohy, tým lepšie.

Vzorové riešenie je teda podobné ako pre Turnaj Mladých Šachistov, len sa trochu viac zahráme s tým, čo vlastne musíme urobiť, aby sme vedeli povedať, ktorý kráľ je v ohrození a ako sa vie zachrániť. Pri skúšaní všetkých možných pohybov figúrok nám totiž veľká väčšina pokusov bude nanič – nás zakaždým zaujíma, či dokážeme vyhodiť jednu predom zvolenú nepriateľskú figúrku, a pritom na overenie tohto berieme postupne všetky naše figúrky, vyskúšame všetky možné pohyby, a potom overujeme, či sme sa náhodou netrafili. Vedeli by sme nejak konkrétnejšie povedať, ktoré figúrky majú šancu na úspech? Kľúč je v tom, že všetky pohyby okrem pešiakov sú symetrické. (Napríklad ak náš kôň ohrozuje nejakú figúrku, tak ak by táto figúrka bola koňom, ohrozovala by toho nášho.)

Zoberme si teda nejakú figúrku a skúsme zistiť, čím je ohrozená. Ak je ohrozená nepriateľským kráľom, ten musí byť na jednom z ôsmich políčok okolo nej. Namiesto toho, aby sme kráľom skúšali jeho osem pohybov, spravíme opak – vyskúšame osem pohybov našou figúrkou, ako keby bola kráľom, a zistíme, či na týchto pozíciách nie je nepriateľský kráľ. Podobne je to s pešiakmi a koňmi – ak našu figúrku ohrozuje nejaký pešiak, ten môže byť len na dvoch možných políčkach, a kôň na ôsmich – vyskúšame teda týchto dokopy \(10\) pozícií, či sa práve na nich nenachádza konkrétne táto nepriateľská figúrka, a ak áno, našli sme figúrku, ktorá nás ohrozuje. Teda zatiaľ namiesto toho aby sme všetkými nepriateľskými koňmi, pešiakmi a kráľom skúšali vyhodiť nami zvolenú figúrku, stačí sa pozrieť na \(8+2+8\) pozící okolo nej a vieme presne povedať či, koľko, a skadiaľ nás figúrky tohto typu ohrozujú.

Rovnaká úvaha zafunguje aj pre typy figúrok, ktoré sa pohybujú donekonečna v niektorých smeroch. Ak nás totiž ohrozuje nejaký strelec, ten musí byť v jednom zo štyroch smerov od našej figúrky, a navyše to musí byť prvá figúrka v tomto smere. Od nami zvolenej figúrky sa nám teda stačí pozrieť do všetkých ôsmich smerov, nájsť prvú figúrku na ktorú v tomto smere narazíme, a zistiť či sa táto figúrka dokáže v tomto smere donekonečna pohybovať – ak áno, ohrozuje nás. Samozrejme, vzhľadom na rozmery šachovnice túto časť už nestíhame simulovať krok po kroku; namiesto toho budeme pozerať na susedné figúrky v nami predpočítaných setoch.

Ak by sme teda chceli zistiť, či kolmo vľavo je alebo nie je ohrozujúca figúrka, tak najprv po načítaní vstupu vytvoríme pole setov veľkosti \(n\), s tým, že set na pozícií \(i\) v sebe bude udržiavať figúrky s \(y\)-ovou súradnicou rovnou \(i\), zoradené podľa ich \(x\)-ovej súradnice. Teraz v sete, v ktorej je umiestnená naša figúrka, ju vyhľadáme a pozrieme sa, čo sa v ňom nachádza pred našou figúrkou – ak tam je nepriateľská figúrka, o ktorej máme zaznamenané že je typu ‘neobmedzený pohyb’ a má povolený pohyb vpravo, tak nás ohrozuje. Analogicky, figúrka, ktorá je za našou figúrkou v tomto sete nás ohrozuje, ak má povolený pohyb vľavo.

Spolu s týmto poľom setov, ktoré používame na overovanie ohrozenia figúrky zľava a sprava, si vytvoríme pole setov na overovanie ohrozenia zhora a zdola (v sete budú figúrky usporiadané podľa \(y\)-ovej súradnice, a figúrku umiestnime do setu zodpovedajúcemu jej \(x\)-ovej súradnici), a pole setov reprezentujúcich diagonálu idúcu zľava hore doprava dole, a diagonálu idúcu zľava dole doprava hore. V každom z týchto setov si potom nájdeme našu figúrku, pozrieme sa na jej predchodcu a jej následníka, a overíme, či je to nepriateľská figúrka, ktorá sa vie hýbať v našom smere; ak áno, ohrozuje nás.

Overenie či je figúrka ohrozená nás teda stojí zhruba toľkoto operácii: \(18 = O(1)\) (overenie konkrétnych pozícií na ktorých môže byť ohrozujúci kráľ, kôň, či pešiak) \(+ O(4 \log f)\) (v štyroch setoch vyhľadáme našu figúrku a pozrieme sa na predchodcu a následníka)

Vytvorenie štyroch polí setov a vloženie figúrok do nich nám na začiatku zaberie \(O(n + f \log f)\) času.

Ostáva nám teda vymyslieť, ako vieme efektívnu funkciu ‘koľko figúrok ma ohrozuje’ využiť na vyriešenie celej úlohy. Najprv si teda zistíme, koľko figúrok ohrozuje bieleho a čierneho kráľa – ak sú ohrození alebo neohrození obaja, povieme príslušnú hlášku. Zaujímavé to teda je, ak je ohrozený práve jeden kráľ. Vtedy máme dve možnosti:

Prvá je pohnúť sa s kráľom, čím ho možno dostaneme z ohrozenia. To už s našou funkciou hravo zvládneme – vyskúšame všetky možné pohyby kráľa (pri ktorých ho najprv zmažeme zo všetkých štruktúr a potom naspäť pridáme s novými súradnicami), a po každom pohybe sa spýtame, či je kráľ ohrozený. Ak nie je, našli sme jeden platný ťah.

Druhá možnosť je zobrať inú priateľskú figúrku a pohnúť ňou tak, aby buď vyhodila alebo sa postavila do cesty tej figúrke, ktorá ohrozuje kráľa. Všimnite si, že toto sa ozaj dá spraviť iba ak kráľa ohrozuje práve jedna nepriateľská figúrka – ak ho totiž ohrozuje viacero, ich cesty ku kráľovi nemajú spoločný bod, a tak žiadnym pohnutím inou figúrkou nevieme súčasne ochrániť kráľa od viac ako jednej figúrky. Zoberme si teda tú figúrku, ktorá ohrozuje kráľa. To, že ho ‘ohrozuje’ vlastne znamená to, že má taký pohyb, ktorým sa vie presunúť na políčko s kráľom. Ak umiestnime ľubovoľnú figúrku (okrem kráľa) na hociktoré políčko na tejto ceste, vrátane začiatočnej pozície tejto figúrky, tak jej vlastne zabránime kráľa vyhodiť. Táto cesta od nepriateľskej figúrky ku kráľovi nie je dlhšia ako \(n\) políčok. Čo si teda môžeme dovoliť robiť je zobrať túto nepriateľskú figúrku, krok po kroku ju posúvať smerom k nášmu kráľovi, a zakaždým sa spýtať či ho nejaká priateľská figúrka neohrozuje. Tieto hodnoty spočítame; ak máme nulu, nevieme kráľa ochrániť, a má mat; inak má šach, a povieme počet platných ťahov, ktoré sme objavili. Ťahov touto nepriateľskou figúrkou spravíme teda \(O(n)\) a každé overenie, koľko našich figúrok ju vie ohroziť, robíme v \(O(\log f)\). Dokopy máme časovú zložitosť \(O(n \log f)\), čo je dostatočne rýchle.

Treba si pritom dať ešte pozor na pár výnimiek.

Za prvé, pri skúšaní ‘vyhodenia’ nepriateľskej figúrky, ktorá ohrozuje kráľa na jej ceste k nemu, v prvom kroku (keď sa ešte nepohla) ju vie priateľský pešiak vyhodiť došikma, avšak vo všetkých ostatných krokoch ju vie vyhodiť len smerom dopredu (keďže táto nepriateľská figúrka reálne nestojí na pozícií, na ktorej sa ju snažíme vyhodiť, iba sa cez neho posúva – pešiak sa na toto prázdne políčko naozaj vie dostať len obyčajným ťahom vpred, nie šikmým).

Za druhé, nesmieme použiť priateľskú figúrku, ktorá ak sa pohne, dovolí inej nepriateľskej figúrke ohrozovať kráľa. Tie nájdeme tak, že keď zisťujeme na začiatku, či sú králi v ohrození, a pri overovaní v jednom smere naďabíme na priateľskú figúrku, pozrieme sa ešte za ňu, a ak tu nájdeme nepriateľskú figúrku ktorá by nás ohrozovala ak by tam naša figúrka nebola prítomná, zaznačíme si na našu figúrku, že ňou nebudeme hýbať.

Nakoniec, predstavte si nasledovnú situáciu: biely kráľ je v strede šachovnice, tri políčka napravo od neho je čierna veža, a napravo od nej je biela veža. Keď budeme čiernou vežou hýbať ku kráľovi, zakaždým nám vyjde, že ju biela veža vie vyhodiť. Avšak bielou vežou máme len jeden platný ťah – vyhodiť čiernu vežu tam, kde najprv stála. Pre každú figúrku si teda ešte zapamätáme, v ktorom smere nám už vyšlo, že vie tohoto nepriateľa vyhodiť, a naozaj zarátame platný ťah len prvý krát pre každý smer.

Upozornenie: slabým náturám môže byť z nasledujúceho kódu nevoľno. Pred pokusmi prehrýzť sa ním odporúčame hlboký nádych a fľašu kofoly. Na úplný záver ešte dodávame, že existuje aj riešenie s časovou zložitosťou \(O(f \log f)\), teda nezávislá na rozmeroch šachovnice. Nechávame ho na premotivovaného čitateľa.

#include <bits/stdc++.h>

using namespace std;

string
white_player = "Biely",
black_player = "Cierny",
impossible = "Nemozna situacia.",
nothing_special = "Neutralna situacia.",
checkmate_msg = " hrac ma mat.",
check_msg = " hrac ma sach. Ma ",
announce_msg = " platnych tahov.";

string answer(string who,int good_moves) //creates answer for check case as a single string
{
    stringstream ss;
    ss << good_moves;
    string ans;
    ss >> ans;
    ans = who + check_msg + ans + announce_msg;
    return ans;
}

struct chesspiece
{
    bool critical = false,colour;
    bool has_killed_in_dir[8] = {false};
    int id,x,y,type,killdir;
    char c;
};

map<pair<int,int>,int> board; //ID of piece on coordinates [x][y]
bool pawns_can_kill; //if true, pawns attempt to attack in is_under_threat(who).
//otherwise, they try to move into the spot
int n,f,typify[500]; //chessboard size, chesspiece #, identification of pieces
chesspiece a_threat;
vector<chesspiece>figurky;
vector< set< pair<int,int> > > row,col,lddiag,rddiag;
// data[pos](coord,id) i.e. row[which row](left to right coord, id)
// row: pos = y, coord = x (left to right) small to large
// column: pos = x, coord = y (small to large = downwards)
// lddiag: pos = x+y, coord = y towards down left (small to large)
// rddiag: pos = x-y+n = [1,2n-1], coord = y towards down right (small to large)

struct movement
{
    vector<int> dx,dy;
};
movement pieces[6];

bool valid(int x,int y)
{
    return (x>=1&&y>=1&&y<=n&&x<=n);
}

void clr() //wipes data from previous testcase
{
    board.clear();
    figurky.clear();
    row.clear();
    col.clear();
    lddiag.clear();
    rddiag.clear();
    pawns_can_kill = true;
}

// checks whether the distance between two pieces is 1, or more
int dist(chesspiece a,chesspiece b)
{
    int x = a.x,y=a.y;
    for(int i=0;i<pieces[0].dx.size();++i)
    {
        int nx = a.x+pieces[0].dx[i];
        int ny = a.y+pieces[0].dy[i];
        if(nx==b.x&&ny==b.y)
            return 1;
    }
    return 2;
}

void preprocess() //intitialize chesspieces,
{
    //typify
    typify[ 'k' ] = typify[ 'K' ] = 0;
    typify[ 'p' ] = typify[ 'P' ] = 1;
    typify[ 'h' ] = typify[ 'H' ] = 2;
    typify[ 'r' ] = typify[ 'R' ] = 3;
    typify[ 'b' ] = typify[ 'B' ] = 4;
    typify[ 'q' ] = typify[ 'Q' ] = 5;


    //hardcoded chessboard pieces

    //king
    pieces[0].dx.push_back(-1);pieces[0].dy.push_back(-1);
    pieces[0].dx.push_back(-1);pieces[0].dy.push_back(0);
    pieces[0].dx.push_back(-1);pieces[0].dy.push_back(1);
    pieces[0].dx.push_back(0);pieces[0].dy.push_back(-1);
    pieces[0].dx.push_back(0);pieces[0].dy.push_back(1);
    pieces[0].dx.push_back(1);pieces[0].dy.push_back(-1);
    pieces[0].dx.push_back(1);pieces[0].dy.push_back(0);
    pieces[0].dx.push_back(1);pieces[0].dy.push_back(1);

    //queen
    pieces[5].dx = pieces[0].dx;
    pieces[5].dy = pieces[0].dy;

    //rook
    pieces[3].dx.push_back(-1);pieces[3].dy.push_back(0);
    pieces[3].dx.push_back(1);pieces[3].dy.push_back(0);
    pieces[3].dx.push_back(0);pieces[3].dy.push_back(-1);
    pieces[3].dx.push_back(0);pieces[3].dy.push_back(1);

    //bishop
    pieces[4].dx.push_back(1);pieces[4].dy.push_back(1);
    pieces[4].dx.push_back(-1);pieces[4].dy.push_back(-1);
    pieces[4].dx.push_back(-1);pieces[4].dy.push_back(1);
    pieces[4].dx.push_back(1);pieces[4].dy.push_back(-1);

    //knight
    pieces[2].dx.push_back(-1);pieces[2].dy.push_back(-2);
    pieces[2].dx.push_back(-2);pieces[2].dy.push_back(-1);
    pieces[2].dx.push_back(-2);pieces[2].dy.push_back(1);
    pieces[2].dx.push_back(-1);pieces[2].dy.push_back(2);
    pieces[2].dx.push_back(1);pieces[2].dy.push_back(2);
    pieces[2].dx.push_back(2);pieces[2].dy.push_back(1);
    pieces[2].dx.push_back(2);pieces[2].dy.push_back(-1);
    pieces[2].dx.push_back(1);pieces[2].dy.push_back(-2);
}

// decides whether chesspiece who can threaten another in the direction how
// if its a king, pathlen has to be 1
int threatens(chesspiece who,pair<int,int> how,int pathlen)
{
    int type = who.type;

    if(type==1||type==2) //pawns and knights are dealt with in parallel.
        return -1;

    if(type==0&&pathlen>1)
        return -1;

    for(int i=0;i<pieces[who.type].dx.size();++i)
    {
        if( pieces[who.type].dx[i] == how.first && pieces[who.type].dy[i] == how.second)
            return i;
    }

    return -1;
}

void vanish(chesspiece who) //deletes 'who' from all sets
{
    board.erase({who.x,who.y});
    col[who.x].erase( {who.y,who.id} );
    row[who.y].erase( {who.x,who.id} );
    lddiag[who.x+who.y].erase( {who.y,who.id} );
    rddiag[who.x-who.y+n].erase( {who.y,who.id} );
}

bool appear(chesspiece who) //inserts 'who' into all sets
{
    if(board.find({who.x,who.y})!=board.end() ) return false;
    //returns true if no collission encountered
    board[{who.x,who.y}] = who.id;
    col[who.x].insert( {who.y,who.id} );
    row[who.y].insert( {who.x,who.id} );
    lddiag[who.x+who.y].insert( {who.y,who.id} );
    rddiag[who.x-who.y+n].insert( {who.y,who.id} );
    return true;
}

bool can_attack(chesspiece a,chesspiece b) //can 'a' kill 'b'?
{
    return(a.colour!=b.colour);
}

int check_set(chesspiece &a_threat, vector< set < pair<int,int> > > &S,
              int lookup,int order,int iterate_dir, pair<int,int>threat_dir,
              chesspiece who,int trial)
{
    /*
    Checks whether the neighbouring chesspiece of 'who' in set S
    in the iteration direction (left,right) = iter_dir contains a
    enemy piece that is able to threaten us in the direction threat_dir.

    Conforms to the use of 'king_trial' specified in is_under_threat,
    i.e. ignores critical pieces if it is set to 0...
    */

    int result = 0;
    set<pair<int,int> >::iterator me,neighbour,dead_end;
    chesspiece threat,crit;
    if(iterate_dir==-1) dead_end = S[lookup].begin();
    else
    {
        dead_end = S[lookup].end();
        dead_end--;
    }
    me = S[lookup].find({order,who.id});
    if(me!=dead_end)
    {
        neighbour = me;
        if(iterate_dir==-1) neighbour--;
        else neighbour++;
        threat = figurky[neighbour->second];
        if(threat.colour != who.colour && (trial!=0 || threat.critical==false) )
        {
            int killdir = threatens(threat,threat_dir,dist(threat,who));
            if(killdir!=-1)
            {
                //A piece can kill another piece in a move in a single direction only once
                //i.e. scenario: a rook threatening the king is lined up with our queen, which
                //thinks it can stop the rook at every point on its path as a unique 'move',
                //when in reality only taking it out in its original position is legitimate
                if(trial==0)
                    if(threat.has_killed_in_dir[killdir]==true) result--;
                    else figurky[neighbour->second].has_killed_in_dir[killdir] = true;

                result++;
                if(trial==1)
                {
                    a_threat = threat;
                    a_threat.killdir = killdir;
                }
            }

        }
        else if (trial == 1 && neighbour!=dead_end)
        {
            crit = threat;
            if(iterate_dir==-1) neighbour--;
            else neighbour++;
            threat = figurky[neighbour->second];
            if(threat.colour!=who.colour && threatens(threat,threat_dir,dist(threat,who))!=-1)
                figurky[crit.id].critical = true;

        }
    }
    return result;
}

int is_under_threat(chesspiece who,int king_trial)
{
    /*
    returns the number of enemy pieces which kill 'who'.

    if king_trial is set to 1, it additionally determines
    the killdir of threats and criticalness of allies, and sets a_threat
    to the last threatening enemy piece found.

    critical enemies are skipped if king_trial is 0.
    */
    int threat_count = 0;

    //check pawns

    int pawndir = 1;
    if(who.colour) pawndir = -1;

    for(int i=0;i<2;++i)
    {
        int dx = 1 - 2*i;
        if(pawns_can_kill==false) dx = 0;
        if(pawns_can_kill==false && i) break;
        if(valid(who.x+dx,who.y+pawndir))
        {
            if(board.find({who.x+dx,who.y+pawndir})==board.end()) continue;
            int id = board[{who.x+dx,who.y+pawndir}];
            if(figurky[id].type!=1) continue;
            if(figurky[id].colour==who.colour) continue;
            if(king_trial==0 && figurky[id].critical) continue;
            threat_count++;
            if(king_trial==1)
            {
                a_threat = figurky[id];
            }
        }
    }


    //check knights

    for(int i=0;i<pieces[2].dx.size();++i)
    {
        int nx = who.x + pieces[2].dx[i];
        int ny = who.y + pieces[2].dy[i];
        if(board.find({nx,ny})!=board.end())
        {
            int id = board[{nx,ny}];
            if(can_attack(figurky[id],who) == false) continue;
            if(figurky[id].type != 2) continue;
            if(king_trial==0 && figurky[id].critical) continue;
            threat_count++;
            if(king_trial==1)
            {
                a_threat = figurky[id];
                a_threat.killdir = i;
            }
        }
    }

    //check all 8 directions

    //up
    threat_count += check_set( a_threat, col, who.x, who.y, -1, {0,1}, who, king_trial);
    //down
    threat_count += check_set( a_threat, col, who.x, who.y,  1, {0,-1}, who, king_trial);
    //left
    threat_count += check_set( a_threat, row, who.y, who.x, -1, {1,0}, who, king_trial);
    //right
    threat_count += check_set( a_threat, row, who.y, who.x,  1, {-1,0}, who, king_trial);
    //left down
    threat_count += check_set( a_threat, lddiag, who.x+who.y , who.y,1,{1,-1},who,king_trial);
    //left up
    threat_count += check_set( a_threat, rddiag, who.x-who.y+n , who.y,-1,{1,1},who,king_trial);
    //right down
    threat_count += check_set( a_threat, rddiag, who.x-who.y+n , who.y,1,{-1,-1},who,king_trial);
    //right up
    threat_count += check_set( a_threat, lddiag, who.x+who.y , who.y,-1,{-1,1},who,king_trial);
    return threat_count;

}

string solve()
{

    clr(); //clear data from previous case
    //read input
    int i,k;
    cin >> n >> f;

    figurky.resize(f);
    col.resize(n+1);
    row.resize(n+1);
    rddiag.resize(n*2+2);
    lddiag.resize(n*2+2);

    chesspiece white,black;
    for(i=0;i<f;++i)
    {
        cin >> figurky[i].x >> figurky[i].y >> figurky[i].c;
        if(isupper( figurky[i].c ) == 0) figurky[i].colour = false;
        else figurky[i].colour = true;
        figurky[i].id = i;
        figurky[i].type = typify[ figurky[i].c ];
        if(figurky[i].c == 'k') white = figurky[i];
        if(figurky[i].c == 'K') black = figurky[i];

    }
    //insert into all 4 sets
    for(i=0;i<f;++i)
    {
        appear(figurky[i]);
        board[ {figurky[i].x,figurky[i].y} ] = i;
    }

    //try both kings
    int wa,ba;
    chesspiece white_killer,black_killer;
    wa = is_under_threat(white,1);
    white_killer = a_threat;
    ba = is_under_threat(black,1);
    black_killer = a_threat;
    if(wa && ba) return impossible;
    if(!wa && !ba) return nothing_special;

    int threats;
    chesspiece killer,king;
    string player;
    if(wa)
    {
        player = white_player;
        king = white;
        threats = wa;
        killer = white_killer;
    }
    else //ba
    {
        player = black_player;
        king = black;
        threats = ba;
        killer = black_killer;
    }
    int good_moves = 0;

    //try all 8 moves

    for(i=0;i<8;++i)
    {
        vanish(king);
        chesspiece temporary_king = king;
        temporary_king.x += pieces[0].dx[i];
        temporary_king.y += pieces[0].dy[i];
        if( valid(temporary_king.x,temporary_king.y) == false )
        {
            appear(king);
            continue;
        }
        if ( appear(temporary_king) )
        {
            if(is_under_threat(temporary_king,2)==0)
                good_moves++;

            vanish(temporary_king);
        }
        else
        {
            chesspiece collission = figurky[ board[ {temporary_king.x,temporary_king.y} ] ];
            if( can_attack(collission,temporary_king))
            {
                vanish(collission);
                appear(temporary_king);
                if(is_under_threat(temporary_king,2)==0)
                    good_moves++;

                vanish(temporary_king);
                appear(collission);
            }
        }

        appear(king);
    }

    if(threats>1)
    {
        if(good_moves == 0) return player + checkmate_msg;
        return answer(player,good_moves);
    }

    figurky[ king.id ].critical = true;
    int tmpkilldir = killer.killdir;
    killer = figurky[ board[ {killer.x,killer.y} ] ];
    killer.killdir = tmpkilldir;
    if(killer.type == 1 || killer.type == 2) //pawns and knights don't move. Either we kill them or we lose.
    {
        good_moves += is_under_threat(killer,0);
        if(good_moves == 0) return player + checkmate_msg;
        return answer(player,good_moves);
    }

    //Try to attack every tile on its path, including itself.
    while(killer.x!=king.x||killer.y!=king.y)
    {
        good_moves += is_under_threat(killer,0);
        pawns_can_kill = false; //killer moved, pawns can't attack new position
        //since he wasn't there originally
        vanish(killer);
        killer.x += pieces[ killer.type].dx[ killer.killdir ];
        killer.y += pieces[ killer.type].dy[ killer.killdir ];

        appear(killer);
    }

    if(good_moves == 0) return player + checkmate_msg;
    return answer(player,good_moves);

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    preprocess();
    int t;
    string tmp;
    cin >> t;
    while(t--) cout << solve() << "\n";

    return 0;
}