#include
#include
#include "map"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "array"
using namespace std;

#define NULL (0)

#define OUT_X (0b1111)
#define OUT_POS (0b11111111)
#define OUT_BLK (0b11111111111111111111111111111111)

#define get_x_from_pos(pos) (((pos)>>4)&0b1111)
#define get_y_from_pos(pos) ((pos)&0b1111)

#define get_pos_from_xy(x,y) (((x)<<4)|(y))

#define get_u_pos_from_blk(stBlk) (((stBlk)>>24)&0b11111111)
#define get_d_pos_from_blk(stBlk) (((stBlk)>>16)&0b11111111)
#define get_l_pos_from_blk(stBlk) (((stBlk)>>8)&0b11111111)
#define get_r_pos_from_blk(stBlk) ((stBlk)&0b11111111)

#define get_blk_from_pos_u_d_l_r(u,d,l,r) (((u)<<24)|((d)<<16)|((l)<<8)|(r))

#define set_u_pos_in_blk(stBlk,pos) ((stBlk)=(((stBlk)&0b00000000111111111111111111111111)|(pos<<24)))
#define set_d_pos_in_blk(stBlk,pos) ((stBlk)=(((stBlk)&0b11111111000000001111111111111111)|(pos<<16)))
#define set_l_pos_in_blk(stBlk,pos) ((stBlk)=(((stBlk)&0b11111111111111110000000011111111)|(pos<<8)))
#define set_r_pos_in_blk(stBlk,pos) ((stBlk)=(((stBlk)&0b11111111111111111111111100000000)|(pos)))

typedef unsigned char pos;
typedef unsigned int stBlk;
typedef unsigned int color;

// global
array, 10> g_initColorMap;
array, 10> g_initStateMap;
pos g_initHeadPos;
map, 10>, int> g_SCORE;
int g_BEST_SCORE;
int g_mapSize, g_mapSize_old;

void globalInit()
{
for (int i=1;i<=10;++i) g_initColorMap[i].fill(0);
for (int i=1;i<=10;++i) g_initStateMap[i].fill(0);
g_initHeadPos = 0;
g_SCORE.clear();
g_BEST_SCORE = 1;
g_mapSize = 0;
g_mapSize_old = 0;
}

void readInitMap()
{
/*
2441353511
2122511244
3444543422
2131423443
4241445212
1122411534
1251131145
2441444415
4254453131
3321521455
*/
string x = "2441353511212251124434445434222131423443424144521211224115341251131145244144441542544531313321521455";
// read color map
for (int i=0; i<=9; ++i) {
for (int j=0; j<=9; ++j) {
g_initColorMap[i][j] = x[i+10*(9-j)]-'0';
}
}
// init state map
for (int i=0; i<=9; ++i) {
for (int j=0; j<=9; ++j) {
pos up, down, left, right;
if (j==9) up = OUT_POS; else up = get_pos_from_xy(i, j+1);
if (j==0) down = OUT_POS; else down = get_pos_from_xy(i, j-1);
if (i==0) left = OUT_POS; else left = get_pos_from_xy(i-1, j);
if (i==9) right = OUT_POS; else right = get_pos_from_xy(i+1, j);
//printf("g_initStateMap[%d][%d]=(%d,%d),(%d,%d),(%d,%d),(%d,%d)\n", i, j, \
get_x_from_pos(up), get_y_from_pos(up), \
get_x_from_pos(down), get_y_from_pos(down), \
get_x_from_pos(left), get_y_from_pos(left), \
get_x_from_pos(right), get_y_from_pos(right));
g_initStateMap[i][j] = get_blk_from_pos_u_d_l_r(up, down, left, right);
}
}
g_initHeadPos = get_pos_from_xy(0, 0);
}

void printMap(array, 10> stMp, pos RealHeadPos)
{
if (stMp[get_x_from_pos(RealHeadPos)][get_y_from_pos(RealHeadPos)] == 0) {
printf("printMap ERROR, RealHeadPos is NULL (%d,%d)\n", get_x_from_pos(RealHeadPos), get_y_from_pos(RealHeadPos));
return;
}
array, 10> temp;
for (int i=0; i<10; ++i) temp[i].fill(0);
pos temp2[10][10];
for(int i=0; i<10; ++i) for(int j=0; j<10; ++j) {
temp2[i][j] = OUT_POS;
}

int xx = 0;  
pos p = RealHeadPos;  
while (p!=OUT\_POS) {  
    xx++;  
    pos q = p;  
    int yy = 0;  
    while (q!=OUT\_POS) {  
        yy++;  
        char qx = get\_x\_from\_pos(q);  
        char qy = get\_y\_from\_pos(q);  
        temp\[xx-1\]\[yy-1\] = g\_initColorMap\[qx\]\[qy\];  
        temp2\[xx-1\]\[yy-1\] = q;  
        q = get\_u\_pos\_from\_blk(stMp\[qx\]\[qy\]);  
    }  
    p = get\_r\_pos\_from\_blk(stMp\[get\_x\_from\_pos(p)\]\[get\_y\_from\_pos(p)\]);  
}

cout << "Head Pos: (" << get\_x\_from\_pos(RealHeadPos) << "," << get\_y\_from\_pos(RealHeadPos) << ")" << endl;  
for (int j=9; j>=0; --j) {  
    for (int i=0; i<=9; ++i) {  
    //if (temp\[i\]\[j\] == 0) cout<<" "; else cout<<temp\[i\]\[j\];  
    if (temp2\[i\]\[j\] == OUT\_POS) printf("      "); else printf("(%d,%d) ",get\_x\_from\_pos(temp2\[i\]\[j\]),get\_y\_from\_pos(temp2\[i\]\[j\]));  
}  
    cout<<endl;  
}  
cout<<endl;  

}

void tickOneBlk(array, 10> &S, pos &Hp, pos tickP)
{
char tickPx = get_x_from_pos(tickP);
char tickPy = get_y_from_pos(tickP);

stBlk tickBlk = S\[tickPx\]\[tickPy\];  
if (tickBlk == 0) {  
        for(int i=0;i<1000;++i) cout <<"fuck"<<endl;  
        return;  
}

pos up = get\_u\_pos\_from\_blk(tickBlk);  
char upx = get\_x\_from\_pos(up);  
char upy = get\_y\_from\_pos(up);  
pos dp = get\_d\_pos\_from\_blk(tickBlk);  
char dpx = get\_x\_from\_pos(dp);  
char dpy = get\_y\_from\_pos(dp);

// at least 1 block below it.  
if (dp != OUT\_POS) {  
    if (up == OUT\_POS) {  
        set\_u\_pos\_in\_blk(S\[dpx\]\[dpy\], OUT\_POS);  
    }  
    else {  
        set\_u\_pos\_in\_blk(S\[dpx\]\[dpy\], up);  
        set\_d\_pos\_in\_blk(S\[upx\]\[upy\], dp);  
    }  
}  
else if (dp == OUT\_POS) { // it's the bottom block  
    pos lp = get\_l\_pos\_from\_blk(tickBlk);  
    char lpx = get\_x\_from\_pos(lp);  
    char lpy = get\_y\_from\_pos(lp);  
    pos rp = get\_r\_pos\_from\_blk(tickBlk);  
    char rpx = get\_x\_from\_pos(rp);  
    char rpy = get\_y\_from\_pos(rp);  
    if (up == OUT\_POS) {  
        if (lp != OUT\_POS) {  
            if (rp == OUT\_POS) {  
                set\_r\_pos\_in\_blk(S\[lpx\]\[lpy\], OUT\_POS);  
            }  
            else if (rp != OUT\_POS) {  
                set\_l\_pos\_in\_blk(S\[rpx\]\[rpy\], lp);  
                set\_r\_pos\_in\_blk(S\[lpx\]\[lpy\], rp);  
            }  
        }  
        else if (lp == OUT\_POS) {  
            if (rp == OUT\_POS) {  
                Hp = OUT\_POS;  
            }  
            else if (rp != OUT\_POS) {  
                set\_l\_pos\_in\_blk(S\[rpx\]\[rpy\], OUT\_POS);  
                Hp = rp;  
            }  
        }  
    }  
    else if (up != OUT\_POS){  
        if (lp != OUT\_POS) {  
            if (rp == OUT\_POS) {  
                set\_r\_pos\_in\_blk(S\[lpx\]\[lpy\], up);  
                set\_d\_pos\_in\_blk(S\[upx\]\[upy\], dp);  
                set\_l\_pos\_in\_blk(S\[upx\]\[upy\], lp);  
                set\_r\_pos\_in\_blk(S\[upx\]\[upy\], rp);  
            }  
            else if (rp != OUT\_POS) {  
                set\_r\_pos\_in\_blk(S\[lpx\]\[lpy\], up);  
                set\_d\_pos\_in\_blk(S\[upx\]\[upy\], dp);  
                set\_l\_pos\_in\_blk(S\[upx\]\[upy\], lp);  
                set\_r\_pos\_in\_blk(S\[upx\]\[upy\], rp);  
                set\_l\_pos\_in\_blk(S\[rpx\]\[rpy\], up);  
            }  
        }  
        else if (lp == OUT\_POS) {  
            if (rp == OUT\_POS) {  
                set\_d\_pos\_in\_blk(S\[upx\]\[upy\], dp);  
                set\_l\_pos\_in\_blk(S\[upx\]\[upy\], lp);  
                set\_r\_pos\_in\_blk(S\[upx\]\[upy\], rp);  
                Hp = up;  
            }  
            else if (rp != OUT\_POS) {  
                set\_d\_pos\_in\_blk(S\[upx\]\[upy\], dp);  
                set\_r\_pos\_in\_blk(S\[upx\]\[upy\], rp);  
                set\_l\_pos\_in\_blk(S\[upx\]\[upy\], lp);  
                set\_l\_pos\_in\_blk(S\[rpx\]\[rpy\], up);  
                Hp = up;  
            }  
        }  
    }  
}  
// destroy this block  
S\[tickPx\]\[tickPy\] = 0;  
//printMap(S, Hp);  

}

void printInfo(pos p, stBlk pb)
{
printf("p:(%d,%d)\n", get_x_from_pos(p), get_y_from_pos(p));
pos up = get_u_pos_from_blk(pb);
pos dp = get_d_pos_from_blk(pb);
pos lp = get_l_pos_from_blk(pb);
pos rp = get_r_pos_from_blk(pb);
printf("up:(%d,%d)\n", get_x_from_pos(up), get_y_from_pos(up));
printf("dp:(%d,%d)\n", get_x_from_pos(dp), get_y_from_pos(dp));
printf("lp:(%d,%d)\n", get_x_from_pos(lp), get_y_from_pos(lp));
printf("rp:(%d,%d)\n", get_x_from_pos(rp), get_y_from_pos(rp));
}
void updateAllPos(array, 10> &state, pos &RealHeadPos)
{
array, 10> temp;
//for (int i=0; i<10; ++i) temp[i].fill(0);
for(int i=0; i<10; ++i) for(int j=0; j<10; ++j) temp[i][j] = OUT_POS;

int xx1 = 0;  
pos p1 = RealHeadPos;  
while (p1 != OUT\_POS) {  
    xx1++;  
    pos q1 = p1;  
    int yy1 = 0;  
    //cout<<"fuck1"<<endl;  
    while (q1 != OUT\_POS) {  
        //printf("%d\\n", RealHeadPos);  
        yy1++;  
        //printMap(state, RealHeadPos);  
        //printf("in p1=(%d,%d) q1=(%d,%d)\\n",get\_x\_from\_pos(p1), get\_y\_from\_pos(p1), get\_x\_from\_pos(q1), get\_y\_from\_pos(q1));  
        //printInfo(p1, state\[get\_x\_from\_pos(p1)\]\[get\_y\_from\_pos(p1)\]);  
        //printInfo(q1, state\[get\_x\_from\_pos(q1)\]\[get\_y\_from\_pos(q1)\]);  
        temp\[xx1-1\]\[yy1-1\] = q1;  
        q1 = get\_u\_pos\_from\_blk(state\[get\_x\_from\_pos(q1)\]\[get\_y\_from\_pos(q1)\]);  
    }  
    p1 = get\_r\_pos\_from\_blk(state\[get\_x\_from\_pos(p1)\]\[get\_y\_from\_pos(p1)\]);  
    //printf("out p1=(%d,%d) q1=(%d,%d)\\n",get\_x\_from\_pos(p1), get\_y\_from\_pos(p1), get\_x\_from\_pos(q1), get\_y\_from\_pos(q1));  
}  
//printf("im out.\\n");  
for(int x=0; x<10; ++x) {  
    if (OUT\_POS == temp\[x\]\[0\]) {  
        break;  
    }  
    for(int y=0; y<10; ++y) {  
        if (OUT\_POS == temp\[x\]\[y\]) {  
            break;  
        }  
        //temp\[x\]\[y\]--;  
        if (9 == y) {  
            set\_u\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], OUT\_POS);  
        }  
        else {  
            set\_u\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], temp\[x\]\[y+1\]);  
        }  
        if (0 == y) {  
            set\_d\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], OUT\_POS);  
        }  
        else {  
            set\_d\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], temp\[x\]\[y-1\]);  
        }  
        if (0 == x) {  
            set\_l\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], OUT\_POS);  
        }  
        else {  
            set\_l\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], temp\[x-1\]\[y\]);  
        }  
        if (9 == x) {  
            set\_r\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], OUT\_POS);  
        }  
        else {  
            set\_r\_pos\_in\_blk(state\[get\_x\_from\_pos(temp\[x\]\[y\])\]\[get\_y\_from\_pos(temp\[x\]\[y\])\], temp\[x+1\]\[y\]);  
        }  
    }  
}  
return;  

}

bool checkIsSingle(array, 10> &state, pos &ckPos)
{
char ck_x = get_x_from_pos(ckPos);
char ck_y = get_y_from_pos(ckPos);

color cx = g\_initColorMap\[ck\_x\]\[ck\_y\];  
stBlk bx = state\[ck\_x\]\[ck\_y\];

pos up = get\_u\_pos\_from\_blk(bx);  
if (up!=OUT\_POS && g\_initColorMap\[get\_x\_from\_pos(up)\]\[get\_y\_from\_pos(up)\]==cx){  
    return false;  
}  
pos dp = get\_d\_pos\_from\_blk(bx);  
if (dp!=OUT\_POS && g\_initColorMap\[get\_x\_from\_pos(dp)\]\[get\_y\_from\_pos(dp)\]==cx){  
    return false;  
}  
pos lp = get\_l\_pos\_from\_blk(bx);  
if (lp!=OUT\_POS && g\_initColorMap\[get\_x\_from\_pos(lp)\]\[get\_y\_from\_pos(lp)\]==cx){  
    return false;  
}  
pos rp = get\_r\_pos\_from\_blk(bx);  
if (rp!=OUT\_POS && g\_initColorMap\[get\_x\_from\_pos(rp)\]\[get\_y\_from\_pos(rp)\]==cx){  
    return false;  
}

return true;  

}

int destroy(array, 10> &state, pos &realHeadPos, pos realTickPos, array, 10> &tmpState, pos &tmpRealHeadPos)
{
pos toTick[105];
int head=0, tail=1;
toTick[tail] = realTickPos;

bool vis\[257\];  
for(int i=0; i<257; ++i) vis\[i\] = 0;  
vis\[realTickPos\] = 1;

while (head < tail) {  
    pos pp = toTick\[++head\];  
    char ppx = get\_x\_from\_pos(pp);  
    char ppy = get\_y\_from\_pos(pp);  
    color pc = g\_initColorMap\[ppx\]\[ppy\];

    stBlk ppb = state\[ppx\]\[ppy\];  
    pos up = get\_u\_pos\_from\_blk(ppb);  
    if (up!=OUT\_POS && !vis\[up\] && g\_initColorMap\[get\_x\_from\_pos(up)\]\[get\_y\_from\_pos(up)\]==pc){  
        vis\[up\] = 1;  
        toTick\[++tail\] = up;  
    }  
    pos dp = get\_d\_pos\_from\_blk(ppb);  
    if (dp!=OUT\_POS && !vis\[dp\] && g\_initColorMap\[get\_x\_from\_pos(dp)\]\[get\_y\_from\_pos(dp)\]==pc){  
        vis\[dp\] = 1;  
        toTick\[++tail\] = dp;  
    }  
    pos lp = get\_l\_pos\_from\_blk(ppb);  
    if (lp!=OUT\_POS && !vis\[lp\] && g\_initColorMap\[get\_x\_from\_pos(lp)\]\[get\_y\_from\_pos(lp)\]==pc){  
        vis\[lp\] = 1;  
        toTick\[++tail\] = lp;  
    }  
    pos rp = get\_r\_pos\_from\_blk(ppb);  
    if (rp!=OUT\_POS && !vis\[rp\] && g\_initColorMap\[get\_x\_from\_pos(rp)\]\[get\_y\_from\_pos(rp)\]==pc){  
        vis\[rp\] = 1;  
        toTick\[++tail\] = rp;  
    }  
}  
for(int i=1; i<=tail; ++i) {  
    tickOneBlk(state, realHeadPos, toTick\[i\]);  
    tickOneBlk(tmpState, tmpRealHeadPos, toTick\[i\]);  
}  
return tail;  

}

int explore(array, 10> state, pos RealHeadPos)
{
//cout<<RealHeadPos<<endl;
int sco = g_SCORE[state];
if ( sco != 0 ) {
return sco;
}

//printMap(state, RealHeadPos);  
updateAllPos(state, RealHeadPos);

array<array<stBlk, 10>, 10> tmpState = state;  
pos tmpRealHeadPos = RealHeadPos;  
int tmpMax = 1;

while (tmpRealHeadPos != OUT\_POS) {  
    if (checkIsSingle(state, tmpRealHeadPos) == true) {  
        tickOneBlk(tmpState, tmpRealHeadPos, tmpRealHeadPos);  
    }  
    else {  
        array<array<stBlk, 10>, 10> state1 = state;  
        pos RealHeadPos1 = RealHeadPos;  
        pos RealTickPos = tmpRealHeadPos;  
        int cnt = destroy(state1, RealHeadPos1, RealTickPos, tmpState, tmpRealHeadPos);  
        tmpMax = max(tmpMax, explore(state1, RealHeadPos1)+5\*cnt\*cnt);  
    }  
}  
g\_SCORE\[state\] = tmpMax;  

#if 0
g_mapSize++;
#endif
if(tmpMax > g_BEST_SCORE) {
g_BEST_SCORE = tmpMax;
cout << "---------------------------" << endl;
cout << "Best Score: " << g_BEST_SCORE << endl;
printMap(state, RealHeadPos);
//g_BEST_SCORE = 999999;
}
//printt(state, g_BEST_SCORE);
return tmpMax;
}

void proc()
{
g_BEST_SCORE = explore(g_initStateMap, g_initHeadPos);
cout << "BEST SCORE :" << g_BEST_SCORE << endl;
}

void random(pos a[], int n)
{
srand((unsigned)time(NULL));
for(int i=0; i<n; ++i) {
int index = rand()%(n-i)+i;
if (index != i) {
pos tmp = a[i];
a[i] = a[index];
a[index] = tmp;
}
}
}

void test(array, 10> S, pos H)
{
pos tick[100];
for(int i=0; i<100; ++i) {
tick[i] = get_pos_from_xy(i/10, i%10);
}
random(tick, 100);
for(int i=0; i<100; ++i) {
int x;

    stBlk tB = S\[get\_x\_from\_pos(tick\[i\])\]\[get\_y\_from\_pos(tick\[i\])\];  
    pos uu = get\_u\_pos\_from\_blk(tB);  
    pos dd = get\_d\_pos\_from\_blk(tB);  
    pos ll = get\_l\_pos\_from\_blk(tB);  
    pos rr = get\_r\_pos\_from\_blk(tB);  
    printf("-----------------------------\\n");  
    printf("tick on (%d, %d)\\n", get\_x\_from\_pos(tick\[i\]), get\_y\_from\_pos(tick\[i\]));  
    printf("u:(%d,%d) d:(%d,%d) l:(%d,%d) r:(%d,%d)\\n",\\  
           get\_x\_from\_pos(uu), get\_y\_from\_pos(uu),\\  
           get\_x\_from\_pos(dd), get\_y\_from\_pos(dd),\\  
           get\_x\_from\_pos(ll), get\_y\_from\_pos(ll),\\  
           get\_x\_from\_pos(rr), get\_y\_from\_pos(rr)  
           );  
    //cin >> x;  
    tickOneBlk(S, H, tick\[i\]);  
    printf("tick Done.\\n");  
    //printMap(S, H);  
    printf("printMap Done.\\n");  
}  
cout<<"test done"<<endl;  
printf("%d\\n", H);  
//printMap(S, H);  

}
int main()
{
globalInit();
readInitMap();
printMap(g_initStateMap, g_initHeadPos);
//test(g_initStateMap, g_initHeadPos);
//tickOneBlk(g_initStateMap, g_initHeadPos, get_pos_from_xy(4, 7));
//printMap(g_initStateMap, g_initHeadPos);
proc();

return 0;  

}