//CHYBY: pokud validace ==7 tak vrat BREAK, kolize s kralem a stejna barva = return 2

/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 * Dodelavky:
 *
 *   promena na jezdce
 *   optimalizaec - pokud po expanzi vrátí 1 rovnou celek vrací 1, pokud je na hloubce H-1, uchová výsledek
 *
 *          - možná: pro expanzi natahuBILY hledame prvni 1 pak return 1
 *                                     CERNY hledame prvni >1 pak return cokoli >1
 *                           !!u expanze cernyho si musime pamatovat jestli se nalezla 1, dole ji pak popr. vratime
 *
 *                - hash mapa - zatím jen pro A:  tah -> hloubka; vysledek
 *
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * ULOHA 3 - sachova koncovka
 * Jan Dvorak (dvoraj42)
 * Prace:       1hod   - struktura projektu, hlavicky, parsovani vstupu, reprezentace stavu, vypis, vytvoreni
 *        5.11. 2,5hod - validace stavu -vyhodnotitStav()- + testy rozlozeni
 *        6.11. 1,5hod - vyhodnoceni expandovaneho stavu - zatim jen se slovnimi vypisy
 *        7.11. 2,5hod - expanse stavu
 *       12.11. 6,0hod - predelavky hlavicek a tak, rekurzivni sestup, vypis tahu
 *       17.11. 1,0hod - struktury na ulozeni, promysleni vystupu, dodelavky na tento vystup
 *       -----------------------
 *       19.11. 1,5hod - prechod na novou verzi - skrty v kodu
 */

/**
 * Struktura (bitove pole) majici 32B -> 1 INT a uchova veskere info ktere potrebujeme o stavu hry
 */
typedef struct
{
    unsigned short cernyKralX :3; //pole 7x7 -> 49 pozic, pokryje to 2 na 6
    unsigned short cernyKralY :3;
    
    unsigned short bilyKralX :3;
    unsigned short bilyKralY :3;

    unsigned short bilyPesecX :3; //pozdeji popr. bila dama / jezdec
    unsigned short bilyPesecY :3;
    unsigned short bilyPesecTypFigurky :2; //0 = pesec, 1 = dama, 2 = jezdec

    unsigned short bilaVezX :3;
    unsigned short bilaVezY :3;

    unsigned short cernaVezX :3;
    unsigned short cernaVezY :3;
}stavPlochy;


/**
 * Globalni promenne
 */
unsigned int HLOUBKA;
int pomocnePole[8][8]; //<1,7>   0==8==vyhozeno
int kolizeX,kolizeY; //pozice na ktere doslo pri validaci ke kolizi

stavPlochy matyB[24];int pocetMatyB=0;

/**
 * Hlavicky funkci
 */
void vypisStavNaVystup(stavPlochy,int);
stavPlochy vytvoritStavPlochyZeStringu(char stav[]);
int vyhodnotitStav(stavPlochy,char);
int expandovatStav(stavPlochy, char, int);
void pridatStav(stavPlochy, char);
int vyhodnoceniStavuValidace(stavPlochy *, char, int ,int, int*);
void vytvorPrefix( char prefix[],int delka );
void vytiskniTah(stavPlochy, stavPlochy);

/******************************************************************************/
/**
 * Generovani vsech moznych z pozic z dane pozice
 * Vraci: 0 - neplatny tah, nic nepridej
 *        21 - vrat 1 - bily uprednosnuje mat
 *        //22 - vrat 1, ukonci pruchod
 *        11 - vrat 0 - cerny uprednostnuje nic
 *        //12 - vrat 0, ukonci pruchod
 *        1 - pocettahu++
 *        2 - pocettahuu++, ukonci pruchod
 *        3 analogie k 1,2  navic vysledek==1
 *        4
 *       -1 - ukonci pruchod
 */
int vyhodnotVysl(int vysl, char naTahu, int hloubka, stavPlochy aktualniStav, stavPlochy stav)
{
            if( vysl==0 || vysl==3 )
            {
                int ve;
                char dalsiTah='B'; if( naTahu=='B' )dalsiTah='C';
                
                if( hloubka>1 )ve=expandovatStav(stav, dalsiTah, hloubka-1);else ve=0; //nema cenu expandovat neco co pak vrati jen 0
                if( ve==1 )
                {
                    if( hloubka==HLOUBKA-1 )matyB[ pocetMatyB++ ]=aktualniStav; //uchovani, zde nekoncime                    
                    if( naTahu=='B' )return 21; //probublame nahoru - nema cenu expandovat dalsi od hloubky H-1                           
                    
                    if( vysl==0 )return 3; //cerny pokracuje v hledani 0
                    return 4;
                }

                if( naTahu=='C' )return 11; //prednost niceho pred prohrou                        

                if( vysl==0) return 1; //bily pokracuje v hledani
                return 2;
            }

            if( vysl==2 )return -1;

            return 0; //neplatny tah
}

/******************************************************************************/
/**
 * Generovani vsech moznych z pozic z dane pozice
 * Vraci: 0 - houby s octem, tj. neprukazna pozice
 *        1 - mat bileho - bily dal mat
 *        2 - mat cerneho
 *        3 - pat bileho
 *        4 - pat cerneho
 *        5 - mat bileho Horizont
 *        6 - mat cerneho horizont
 */
int expandovatStav(stavPlochy aktualniStav, char naTahu, int hloubka)
{
    //vyhodnoceni hloubky
    if( hloubka==0 )
    {
        return 0;
    }

    //jsem v sachu?
    int vysl,i,o;
    int bilyVsachu=0,cernyVsachu=0;
    vysl=vyhodnotitStav(aktualniStav,naTahu);
    if( vysl==4 )bilyVsachu=1;
        else if( vysl==5 )cernyVsachu=1;


/*    //vypis
    printf("\nTAH: %c, hloubka: %u; sach na B: %u, C: %u; validace: %u:\n",naTahu,hloubka,bilyVsachu,cernyVsachu,vysl);
    vypisStavNaVystup(aktualniStav,hloubka);
/**/

    //
    int kx,ky,vx,vy,px,py,typ;
    stavPlochy stav;    
    char dalsiTah='B'; if( naTahu=='B' )dalsiTah='C';
    int stavSach=0; //pocet stavu kdyz jsem v sachu v aktualnim stavu a v expandovanym nejsem - tj pokud >0 zbavili jsme se sachu - neni PAT ci MAT               
    int pridanoTahu=0; //kolik policek v poli bylo obsazeno
    int ve;

    //ziskani udaju
    if( naTahu=='B' )
    {
        kx=aktualniStav.bilyKralX;
        ky=aktualniStav.bilyKralY;
        vx=aktualniStav.bilaVezX;
        vy=aktualniStav.bilaVezY;
        px=aktualniStav.bilyPesecX;
        py=aktualniStav.bilyPesecY;
        typ=aktualniStav.bilyPesecTypFigurky;        
        
    }else{
        kx=aktualniStav.cernyKralX;
        ky=aktualniStav.cernyKralY;
        vx=aktualniStav.cernaVezX;
        vy=aktualniStav.cernaVezY;
        px=0; //jakoby vyhozen
        py=0;
        
    }

    //generace tahu - musim kontrolovat mimo plochu uz TADY!!
    int vysledek=0;

    /**
     * KRAL - 8 moznosti
     */    
    //leve 3 tahy
    if( kx>1 )
    {
        stav=aktualniStav;
        if( naTahu=='B' )stav.bilyKralX=kx-1;
                    else stav.cernyKralX=kx-1;
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);        
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        //if( vysl==2 || vysl==4 )break;

        if( ky>1 )
        {
            stav=aktualniStav;
            if( naTahu=='B' ){stav.bilyKralY=ky-1;stav.bilyKralX=kx-1;}
                        else {stav.cernyKralY=ky-1;stav.cernyKralX=kx-1;}
            
            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
            if( vysl>0 )pridanoTahu++;
            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        }

        if( ky<7 )
        {
            stav=aktualniStav;
            if( naTahu=='B' ){stav.bilyKralY=ky+1;stav.bilyKralX=kx-1;}
                        else {stav.cernyKralY=ky+1;stav.cernyKralX=kx-1;}

            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
            if( vysl>0 )pridanoTahu++;
            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        }
        
    }

    //prave 3 tahy
    if( kx<7 )
    {
        stav=aktualniStav;
        if( naTahu=='B' ){stav.bilyKralX=kx+1;}
                    else {stav.cernyKralX=kx+1;}
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4

        if( ky>1 )
        {
            stav=aktualniStav;
            if( naTahu=='B' ){stav.bilyKralX=kx+1;stav.bilyKralY=ky-1;}
                        else {stav.cernyKralX=kx+1;stav.cernyKralY=ky-1;}

            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
            if( vysl>0 )pridanoTahu++;
            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        }

        if( ky<7 )
        {
            stav=aktualniStav;
            if( naTahu=='B' ){stav.bilyKralX=kx+1;stav.bilyKralY=ky+1;}
                        else {stav.cernyKralX=kx+1;stav.cernyKralY=ky+1;}
            
            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
            if( vysl>0 )pridanoTahu++;
            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        }
    }

    //horni tah
    if( ky<7 )
    {
        stav=aktualniStav;
        if( naTahu=='B' )stav.bilyKralY=ky+1;
                    else stav.cernyKralY=ky+1;
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
    }
    
    //spodni tah
    if( ky>1 )
    {
        stav=aktualniStav;    
        if( naTahu=='B' )stav.bilyKralY=ky-1;
                    else stav.cernyKralY=ky-1;
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
    }

    /**
     * VEZ - 12 moznosti
     */
    if( vx>0 ){
        
    //do leva
    for( i=vx-1; i>=1; i-- )
    {
        stav=aktualniStav;
        if( naTahu=='B' )stav.bilaVezX=i;
                    else stav.cernaVezX=i;
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        if( vysl==2 || vysl==4 )break;
    }

    //doprava
    for( i=vx+1; i<=7; i++ )
    {
        stav=aktualniStav;
        if( naTahu=='B' )stav.bilaVezX=i;
                    else stav.cernaVezX=i;
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        if( vysl==2 || vysl==4 )break;
    }

    //nahoru
    for( i=vy+1; i<=7; i++ )
    {
        stav=aktualniStav;
        if( naTahu=='B' )stav.bilaVezY=i;
                    else stav.cernaVezY=i;
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        if( vysl==2 || vysl==4 )break;
    }

    //dolu
    for( i=vy-1; i>=1; i-- )
    {
        stav=aktualniStav;
        if( naTahu=='B' )stav.bilaVezY=i;
                    else stav.cernaVezY=i;
        
        vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
        vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
        if( vysl>0 )pridanoTahu++;
        if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
        if( vysl==2 || vysl==4 )break;
    }

    }//konec podminky existence veze

    if( px>0 && naTahu=='B' )
    {
    /**
     * PESEC - 2 moznosti
     */
    if( typ==0 )
    {
        if( py<7 )
        {
            //nahoru
            stav=aktualniStav;
            stav.bilyPesecY=py+1;

            //promena pesce
            if( stav.bilyPesecY==7 && stav.bilyPesecTypFigurky==0 )
            {
                    stav.bilyPesecTypFigurky=1; //dama
                    //ve=expandovatStav(stav,naTahu,hloubka);
                    //return ve;

                    //dama se nepovedla -> kun
                    //stav.bilyPesecTypFigurky=2; //kun
                    //return expandovatStav(stav,naTahu,hloubka);
            }
            //konec promeny pesce

            
            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
            if( vysl>0 )pridanoTahu++;
            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4

            //vyskoceni - pokud je v boku cizi figurka - zkusime to tam
            stav=aktualniStav;
            stav.bilyPesecX=px+1;
            
            vysl=vyhodnotitStav(stav,naTahu);
            if( vysl==3 )
            {
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
            }
            
            stav=aktualniStav;
            stav.bilyPesecX=px-1;
            
            vysl=vyhodnotitStav(stav,naTahu);
            if( vysl==3 )
            {
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
            }
            
        }
    }

    /**
     * KUN - 8 moznosti - !! kontrolovat mimo plochu
     */
    else if( typ==2 )
    {
        stav=aktualniStav;
        i=px+2;o=py-1; if( i<=7 && o>0 ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;                                            
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }           
        i=px+2;o=py+1; if( i<=7 && o<=7 ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }          
        i=px-2;o=py-1; if( i>0 && o>0   ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }           
        i=px-2;o=py+1; if( i>0 && o<=7  ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }           
        i=px+1;o=py+2; if( i<=7 && o<=7 ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }           
        i=px+1;o=py-2; if( i<=7 && o>0  ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }           
        i=px-1;o=py+2; if( i>0 && o<=7  ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }         
        i=px-1;o=py-2; if( i>0 && o>0   ){ stav=aktualniStav;stav.bilyPesecX=i;stav.bilyPesecY=o;
                                            vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                                            vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                                            if( vysl>0 )pridanoTahu++;
                                            if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                                          }         
    }

    /**
     * DAMA - az 24 moznosti
     */
    else
    {        
        //chovani veze
            //do leva
            for( i=px-1; i>=1; i-- )
            {
                stav=aktualniStav;
                stav.bilyPesecX=i;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
            }

            //doprava
            for( i=px+1; i<=7; i++ )
            {
                stav=aktualniStav;
                stav.bilyPesecX=i;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
            }

            //nahoru
            for( i=py+1; i<=7; i++ )
            {
                stav=aktualniStav;
                stav.bilyPesecY=i;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
            }

            //dolu
            
            for( i=py-1; i>=1; i-- )
            {
                stav=aktualniStav;
                stav.bilyPesecY=i;
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
            }
        //chovani strelce
            //dolu doleva
            i=px-1;o=py-1;
            while( i>0 && o>0 )
            {                
                stav=aktualniStav;
                stav.bilyPesecX=i;stav.bilyPesecY=o;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
                i--;o--;
            }
            //nahoru doleva
            i=px-1;o=py+1;
            while( i>0 && o<=7 )
            {
                stav=aktualniStav;
                stav.bilyPesecX=i;stav.bilyPesecY=o;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
                i--;o++;
            }
            //dolu doprava
            i=px+1;o=py-1;
            while( i<=7 && o>0 )
            {
                stav=aktualniStav;
                stav.bilyPesecX=i;stav.bilyPesecY=o;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
                i++;o--;
            }
            //nahoru doprava
            i=px+1;o=py+1;
            while( i<=7 && o<=7 )
            {
                stav=aktualniStav;
                stav.bilyPesecX=i;stav.bilyPesecY=o;
                
                vysl=vyhodnoceniStavuValidace(&stav,naTahu,bilyVsachu,cernyVsachu,&stavSach);
                vysl=vyhodnotVysl(vysl,naTahu,hloubka,aktualniStav,stav);
                if( vysl>0 )pridanoTahu++;
                if( vysl==21 )return 1; else if( vysl==11 )return 0; else if( vysl>2 )vysledek=1; //3+4
                if( vysl==2 || vysl==4 )break;
                i++;o++;
            }
    }
    //KONEC DAMY
    
    }//END if px>0

    /**
     * VYHODNOCENI GENERATORU
     */

/*VYPIS* /
    int delka=hloubka*3+3;
    char prefix[delka];
    vytvorPrefix( prefix, delka );
    printf("\n%sExpandovano: %u",prefix,pridanoTahu);
    printf("\n%s     :",prefix);
/**/
    
    /**
     * List
     */    
    if( naTahu=='C' )
    {
        if( cernyVsachu==1 && pridanoTahu==0 )
        {
            //VYHRA BILEHO
            //printf("\n%sBILY DAL MAT\n",prefix);            
            if( hloubka==HLOUBKA-1 )matyB[ pocetMatyB++ ]=aktualniStav;
            return 1;

        }else if( pridanoTahu==0 ){
            //cerny nemuze tahnout => PAT CERNEHO
            //printf("\n%sPAT CERNY\n",prefix);
            return 0;
            return 4;
        }

    }else if( naTahu=='B' ){
        if( bilyVsachu==1 && pridanoTahu==0 )
        {
            //VYHRA CERNEHO
            //printf("\n%sCERNY DAL MAT\n",prefix);
            return 0;
            return 2;

        }else if( pridanoTahu==0 ){
            //bily nema kam tahnout => PAT BILEHO
            //printf("\n%sPAT BILY\n",prefix);
            return 0;
            return 3;
        }

    }
    
    //
    return vysledek;
}

/******************************************************************************/
/**
 * MAIN
 */
int main(int argc, char** argv)
{
    //nacteni vstupu
    char vstup[20]; //i s rezervou

    scanf("%[^\n]",vstup);
    scanf("%c"); //konec radky    
    scanf("%u",&HLOUBKA);
    
    stavPlochy start=vytvoritStavPlochyZeStringu(vstup);    

/** /
    printf("Vstup:\n------\n%s\n\n",vstup);
    vypisStavNaVystup(start,HLOUBKA);
    printf("\nNa tahu: %c\n",NATAHU);
    printf("Hloubka: %u",HLOUBKA);
    printf("\n\nVysledek vyhodnoceni stavu: %u\n", vyhodnotitStav(start,NATAHU) );
    printf("\nMaterialni prevaha: %u\n",zjistitMaterialniPrevahu(start));
/**/
    HLOUBKA=HLOUBKA*2;
    expandovatStav(start,'B',HLOUBKA);

/*test vypisu* /
char v1[20],v2[20];

//zmena v damu + sach
v1="Kd5 Vf3 c6 Kf7 Vf6 ";
v2="Kd5 Vf3 Dc7 Kf7 Vf6";
vytiskniTah( vytvoritStavPlochyZeStringu(v1),vytvoritStavPlochyZeStringu(v2) );
/**/
    
    //vyhodnoceni
    int i;
    //priority: mat, matH, nic, pat, vynuceny pat, vynucena prohra
    if( pocetMatyB>0 )
    {
            printf("1-0");
            for( i=0;i<pocetMatyB;i++ )
            {
                printf(" ");
                vytiskniTah(start,matyB[i]);
            }
            printf("\n");

    }else{
        //nevyhral
        printf("Nevyhraje\n");
            
    }

    return 0;
}

/******************************************************************************/
/**
 * Vyhodnoceni stavu validace expandovaneho stavu
 * Vraci:   0 - tah pridan
 *          1 - neplatny tah - pokracovat v generatoru
 *          2 - ukoncit prochazeni dane moznosti - kolize
 *          3 - ukoncit ale pridan tah - vyskocena figurka
 */
int vyhodnoceniStavuValidace(stavPlochy *stav, char naTahu, int bilyVsachu,int cernyVsachu, int *stavSach)
{
    int pridat=0;
    
    //vyhodnoceni validace
    int validace=vyhodnotitStav(*stav,naTahu);
    int sachB=0,sachC=0;

    if( validace==0 )
    {
        if( naTahu=='B' && bilyVsachu )*stavSach++; //zbavili jsme se sachu
            else if( naTahu=='C' && cernyVsachu )*stavSach++;
        pridat=1; //OK tah

    }else if( validace==1 || validace==6 || validace==7 ){
        //NIC
        return 1;

    }else if( validace==2 ){
        //KONEC generovani pozice pro danou figurku !! - optimalizace
        return 2;

    }else if( validace==3 ){
        //Vyskocime figurku
        if( naTahu=='B' ) //vyskocit mohl jen vez
        {
            (*stav).cernaVezX=0;(*stav).cernaVezY=0;

        }else{
            if( kolizeX==(*stav).bilyPesecX && kolizeY==(*stav).bilyPesecY ){ (*stav).bilyPesecX=0;(*stav).bilyPesecY=0; }
                                                                  else{ (*stav).bilaVezX=0;(*stav).bilaVezY=0; }
        }
        //zavolame na ni dalsi tah nyni jiz bez kolize
        int v1=vyhodnoceniStavuValidace(stav, naTahu, bilyVsachu, cernyVsachu, stavSach);
        if( v1==0 || v1==3 )return 3; //pridano + sto
            else return v1;

    }else if( validace==4 ){
        //pokud je sach na ciziho a nejsem v sachu, pridam
        sachB=1;
        if( naTahu=='C' )
        {
            if( cernyVsachu==0 )pridat=1; //OK

        }else return 1;  //hraje bily - //blby tah - musi se zbavit sachu

    }else if( validace==5 ){
        sachC=1;
        //pokud je sach na ciziho a nejsem v sachu, pridam
        if( naTahu=='B' )
        {
            if( bilyVsachu==0 )pridat=1; //OK

        }else return 1; //hraje cerny - //blby tah - musi se zbavit sachu

    }else if( validace==7 ){
        return 1; //nejde skocit krale
    }


    ////pridavame expandovany stav
    if( pridat==1 )return 0;
        else return 1;
}

/******************************************************************************/
/**
 * Pridani stavu do plochy
 */
void pridatStav(stavPlochy stav, char naTahu)
{
    printf("ADD:\n");
    vypisStavNaVystup(stav,HLOUBKA);
}

/******************************************************************************/
/**
 * Vyhodnoceni stavu
 * Vraci:  0 = volno (zadne ohrozeni a pod)
 *         1 = kralove u sebe - chybny tah (gen. pokracuje)
 *         2 = kolize stejnych figurek - generator konci
 *         3 = kolize ruznych figurek - generator prepise stav (vyhodi) a vyhodnoti znovu, pak zkonci
 *         4 = sach na bileho krale
 *         5 = sach na cerneho krale
 *         6 = oba kralove v sachu - chybny stav (gen. pokracuje)
 *         7 = kolize s kralem - chyby stav (nejde vyhodit) - generator konci - logicky nemuze nastat - skakalo by se z sachu
 */
int vyhodnotitStav(stavPlochy stav,char naTahu)
{
    int kx,ky,vx,vy,px,py,typ,Kx,Ky,Vx,Vy;
    kx=stav.bilyKralX;ky=stav.bilyKralY;
    vx=stav.bilaVezX;vy=stav.bilaVezY;
    px=stav.bilyPesecX;py=stav.bilyPesecY;
    typ=stav.bilyPesecTypFigurky;
    Kx=stav.cernyKralX;Ky=stav.cernyKralY;
    Vx=stav.cernaVezX;Vy=stav.cernaVezY;

    /**
     * KOLIZE - 2+3
     */    
    if( vx!=0 )
    {
        if( vx==px && vy==py )return 2;
        if( vx==kx && vy==ky )return 7;
        if( vx==Kx && vy==Ky){ if( naTahu=='B' )return 7; else { kolizeX=vx;kolizeY=vy;return 3;} } //Ck muze vyskocit bilou vez
        if( vx==Vx && vy==Vy){kolizeX=vx;kolizeY=vy;return 3;}
    }
    if( px!=0 )
    {
        if( px==kx && py==ky )return 7;
        if( px==Kx && py==Ky ){ if( naTahu=='B' )return 7; else { kolizeX=px;kolizeY=py;return 3;} } //cerny kral muze skocit bilou figurku
        if( px==Vx && py==Vy ){kolizeX=px;kolizeY=py;return 3;}
    }
    if( Vx!=0 )
    {
        if( Kx==Vx && Ky==Vy )return 7;
        if( kx==Vx && ky==Vy ){ if( naTahu=='C' )return 7; else { kolizeX=Vx;kolizeY=Vy;return 3;} } //bily kral bere cernou vez
    }
    if( Kx==kx && Ky==ky )return 7;

    /**
     * KRALOVE U SEBE - 1
     */
    int i,o;
    i=kx-Kx; if( i<=0 )i=-i;
    o=ky-Ky; if( o<=0 )o=-o;
    if( i<=1 && o<=1 )return 1;

    /**
     * SACH - staci detekce 1 sachu
     */
    int s1=0,s2=0; //1 = bily; s2==1 => sach na cerneho
    for( i=1; i<=7; i++ )for( o=1; o<=7; o++ )pomocnePole[i][o]=0; //POLE = <1,7> (0 pozice vyhozene figurky)
    pomocnePole[kx][ky]=1;
    pomocnePole[vx][vy]=1;
    pomocnePole[px][py]=1;
    pomocnePole[Kx][Ky]=2;
    pomocnePole[Vx][Vy]=2;

    //BV->CK
    if( vx==Kx )
    {
        if( vy<Ky ){ for( i=vy+1; i<Ky; i++ )if( pomocnePole[vx][i]!=0 )break;  if( i==Ky )s2=1; }
               else{ for( i=Ky+1; i<vy; i++ )if( pomocnePole[vx][i]!=0 )break;  if( i==vy )s2=1; }
    }
    if( vy==Ky )
    {
        if( vx<Kx ){ for( i=vx+1; i<Kx; i++ )if( pomocnePole[i][vy]!=0 )break;  if( i==Kx )s2=1; }
               else{ for( i=Kx+1; i<vx; i++ )if( pomocnePole[i][vy]!=0 )break;  if( i==vx )s2=1; }
    }

    //BP->CK:  pesec kral; kun kral; dama kral
    if( typ==0 && s2==0 && px>0 ) //PINCL
    {
        if( (px==Kx-1 || px==Kx+1) && py==Ky-1 )s2=1;

    }else if( typ==1 && s2==0 && px>0 ){ //DAMA
        //chovani veze
        if( px==Kx )
        {
            if( py<Ky ){ for( i=py+1; i<Ky; i++ )if( pomocnePole[px][i]!=0 )break;  if( i==Ky )s2=1; }
                   else{ for( i=Ky+1; i<py; i++ )if( pomocnePole[px][i]!=0 )break;  if( i==py )s2=1; }
        }
        if( py==Ky )
        {
            if( px<Kx ){ for( i=px+1; i<Kx; i++ )if( pomocnePole[i][py]!=0 )break;  if( i==Kx )s2=1; }
                   else{ for( i=Kx+1; i<px; i++ )if( pomocnePole[i][py]!=0 )break;  if( i==px )s2=1; }
        }
        //chovani strelce
        int roz; //o kolik policek se dama hybe ke krali
        roz=px-Kx;          if( roz<=0 )roz=-roz;         o=py-Ky;           if( o<=0 )o=-o;
        if( s2==0 && roz==o) //musi byt od sebe stejne policek po X a Y
        {
            if( px<Kx )
            {
                if( py<Ky )
                {
                    for( i=1; i<roz; i++ )if( pomocnePole[px+i][py+i]!=0 )break;  if( i==roz )s2=1;

                }else{ //py>Ky
                    for( i=1; i<roz; i++ )if( pomocnePole[px+i][py-i]!=0 )break;  if( i==roz )s2=1;
                }

            }else{ //px > Kx
                if( py<Ky )
                {
                    for( i=1; i<roz; i++ )if( pomocnePole[px-i][py+i]!=0 )break;  if( i==roz )s2=1;

                }else{ //py>Ky
                    for( i=1; i<roz; i++ )if( pomocnePole[px-i][py-i]!=0 )break;  if( i==roz )s2=1;
                }
            }
        } //END IF S2==0 ...

    }else if( typ==2 && s2==0 && px>0 ){ //KUN
        //+-2 +-1;  +-1 +-2
        if( (px+2==Kx && py+1==Ky) || (px+2==Kx && py-1==Ky) ||
            (px-2==Kx && py+1==Ky) || (px-2==Kx && py-1==Ky) ||
            (px+1==Kx && py+2==Ky) || (px+1==Kx && py-2==Ky) ||
            (px-1==Kx && py+2==Ky) || (px-1==Kx && py-2==Ky)    )s2=1;
    }

    //CV->BK
    if( Vx==kx )
    {
        if( Vy<ky ){ for( i=Vy+1; i<ky; i++ )if( pomocnePole[Vx][i]!=0 )break;  if( i==ky )s1=1; }
               else{ for( i=ky+1; i<Vy; i++ )if( pomocnePole[Vx][i]!=0 )break;  if( i==Vy )s1=1; }
    }
    if( Vy==ky )
    {
        if( Vx<kx ){ for( i=Vx+1; i<kx; i++ )if( pomocnePole[i][Vy]!=0 )break;  if( i==kx )s1=1; }
               else{ for( i=kx+1; i<Vx; i++ )if( pomocnePole[i][Vy]!=0 )break;  if( i==Vx )s1=1; }
    }

    /**
     * VYHODNOCENI
     */
    if( s1==0 && s2==0 )return 0;
    if( s1==1 && s2==0 )return 4;
    if( s1==0 && s2==1 )return 5;
    return 6;
}

/******************************************************************************/
/**
 * Rozparsovani vstupniho radku na pozici figurek
 */
stavPlochy vytvoritStavPlochyZeStringu(char str[])
{
    stavPlochy vysledek;
    int i;

    //BK
    vysledek.bilyKralX=str[1]-'a'+1;
    vysledek.bilyKralY=str[2]-'0';

    //BV
    i=4;
    if( str[i]=='V'  )
    {
        vysledek.bilaVezX=str[i+1]-'a'+1;
        vysledek.bilaVezY=str[i+2]-'0';
        i+=4;
        
    }else{
        vysledek.bilaVezX=0;
        vysledek.bilaVezY=0;        
    }
    
    //BD
    vysledek.bilyPesecTypFigurky=0;
    if( str[i]=='D' || str[i]=='J')
    {
        vysledek.bilyPesecX=str[i+1]-'a'+1;
        vysledek.bilyPesecY=str[i+2]-'0';
        
        if( str[i]=='D')vysledek.bilyPesecTypFigurky=1;
                   else vysledek.bilyPesecTypFigurky=2;
        i+=4;

    //BP
    }else{
        i--;
        if( str[i+1]=='K' )i++; //pesec neni zadan, ani vez
        if( str[i]!='K' )
        {
            vysledek.bilyPesecX=str[i+1]-'a'+1;
            vysledek.bilyPesecY=str[i+2]-'0';
            i+=4;
        
        }else{
            vysledek.bilyPesecX=0; //za plochou = je vyhozeny
            vysledek.bilyPesecY=0;
        }
    }

    
    //CK
    vysledek.cernyKralX=str[i+1]-'a'+1;
    vysledek.cernyKralY=str[i+2]-'0';
    i+=4;

    if( str[i]=='V' )
    {
        vysledek.cernaVezX=str[i+1]-'a'+1;
        vysledek.cernaVezY=str[i+2]-'0';
    
    }else{
        vysledek.cernaVezX=0;
        vysledek.cernaVezY=0;
    }

    return vysledek;
}

/******************************************************************************/
/**
 * Vypis stavu do konzole
 */

void vytvorPrefix( char prefix[],int delka )
{
    int i;
    for( i=0; i<delka-3; i++)prefix[i]='-';
    prefix[i++]='>';
    prefix[i++]=' ';
    prefix[i]='\0';
}

void vypisStavNaVystup(stavPlochy stav,int odsazeni)
{
    int delka=odsazeni*3+3;
    char prefix[delka];
    vytvorPrefix( prefix, delka );
    
    printf("%sBILY:\n%s-----\n",prefix,prefix);
    printf("%sK: [%u,%u]\n",prefix,stav.bilyKralX,stav.bilyKralY);
    printf("%sV: [%u,%u]\n",prefix,stav.bilaVezX, stav.bilaVezY);
    printf("%s[%u,%u](%u)\n\n",prefix, stav.bilyPesecX, stav.bilyPesecY, stav.bilyPesecTypFigurky);

    printf("%sCERNY:\n%s-----\n",prefix,prefix);
    printf("%sK: [%u,%u]\n",prefix,stav.cernyKralX,stav.cernyKralY);
    printf("%sV: [%u,%u]\n",prefix,stav.cernaVezX, stav.cernaVezY);
}

/******************************************************************************/
/**
 * Vypis tahu
 */
void vytiskniTah(stavPlochy start, stavPlochy cil)
{
    char figurka;int naX, naY;
    char naTahu='B';    
    if( (start.bilaVezX!=cil.bilaVezX || start.bilaVezY!=cil.bilaVezY) && cil.bilaVezX!=0 ){figurka='V';naX=cil.bilaVezX;naY=cil.bilaVezY;}
    else if( (start.bilyKralX!=cil.bilyKralX || start.bilyKralY!=cil.bilyKralY) ){figurka='K';naX=cil.bilyKralX;naY=cil.bilyKralY;}
    else if( (start.bilyPesecX!=cil.bilyPesecX || start.bilyPesecY!=cil.bilyPesecY) && cil.bilyPesecX!=0 )
    {
        naX=cil.bilyPesecX;naY=cil.bilyPesecY;
        if( start.bilyPesecTypFigurky==0 )figurka='\0';
            else if( start.bilyPesecTypFigurky==1 )figurka='D';
            else figurka='J';
    }

    else if( (start.cernaVezX!=cil.cernaVezX || start.cernaVezY!=cil.cernaVezY) && cil.cernaVezX!=0 ){figurka='V';naX=cil.cernaVezX;naY=cil.cernaVezY;naTahu='C';}
    else if( (start.cernyKralX!=cil.cernyKralX || start.cernyKralY!=cil.cernyKralY) ){figurka='K';naX=cil.cernyKralX;naY=cil.cernyKralY;naTahu='C';}


    //vypis       
    if( figurka!='\0' )printf("%c",figurka);
    printf("%c%u",'a'-1+naX,naY);
}