#include <iostream>

#include <time.h>

#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<array<color, 10>, 10>                 g_initColorMap;

array<array<stBlk, 10>, 10>                 g_initStateMap;

pos                                         g_initHeadPos;

map<array<array<stBlk, 10>, 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<array<stBlk, 10>, 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<array<color, 10>, 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<array<stBlk, 10>, 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<array<stBlk, 10>, 10> &state, pos &RealHeadPos)

{

    array<array<pos, 10>, 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<array<stBlk, 10>, 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<array<stBlk, 10>, 10> &state, pos &realHeadPos, pos realTickPos, array<array<stBlk, 10>, 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<array<stBlk, 10>, 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<array<stBlk, 10>, 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;

}

最新文章

  1. HTML5实战与剖析之触摸事件(touchstart、touchmove和touchend)
  2. Setup Apache + PHP + MySql on Windows 10
  3. android 自定义弹出框AlertDialog ，很炫的哦
  4. Maven 的41种骨架
  5. Oracle出现字符集问题处理方法
  6. 基于CentOS与VmwareStation10搭建Oracle11G RAC 64集群环境：1.资源准备
  7. shell 学习笔记
  8. Deployed component GUIs and figures have different look and feel than MATLAB desktop
  9. zookeeper配置同步zookeeper编程
  10. BeagleBone Black教训四局：简单LED对照实验
  11. 【剑指offer】最小的k的数量
  12. [原创]SecureCRT终端软件连接VMware Workstation Pro虚拟机
  13. JS的异步世界
  14. 12.利用kakatips对网站数据信息监控
  15. Appium appium 安装不了
  16. XML Publisher 并发程序由于&quot;输出提交处理程序提交失败
  17. windows 64位下 Octave 不能画图的解决办法
  18. 迭代dict的key和value
  19. 高性能.NET MVC之QMVC!
  20. Data_Structure04-树

热门文章

  1. Django学习day05随堂笔记
  2. Jenkins 进阶篇 - 任务关联
  3. PHP多文件上传格式化
  4. MSSQL数据库安全实验
  5. three.js 添加html内容、文本
  6. P5305-[GXOI/GZOI2019]旧词【树链剖分,线段树】
  7. 基于python深度学习的apk风险预测脚本
  8. DL4J实战之二：鸢尾花分类
  9. SpringBoot之网站的登陆注册逻辑
  10. ubuntu20.04安装网易云音乐