Klotski2

---

数据结构作业 华容道

上次没看到还要自动玩的功能…

效果什么的看上次的
上一份

---

和上次的区别大概是
play函数,main函数
play和main之间的
多了100多行(一半是空行)
还有多一个头文件”queue”

---

(老师是梁宝兰的别拿走)
(怕你拿去交了)

---

代码:

#include <graphics.h>
#include <conio.h>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <queue>

struct pic {
    IMAGE src;  //用于输出图片
    int x, y;   //现在的坐标
    int id;     //原始编号
} photo[10];

//为了获得图片路径,然后就没用了
char path_temp[] = "img\\0.jpg";
TCHAR path[10];

//记录当前格子是哪张图片
int map[4][4] = { { -1, 0, -1, -1 },
                { -1, 1, 2, 3 },
                { -1, 4, 5, 6 },
                { -1, 7, 8, 9 } };

//四个方向
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

//记录黑色图片在哪(在map的位置)
int nowx, nowy;

//记录步数
int step;
char text[25];
TCHAR out[25];

//输出步数
void print_step() {
    sprintf(text, "%d step!", step);
    for (int i = 0; '\0' != text[i]; ++i)
        out[i] = text[i];
    outtextxy(-170, -200, out);
}

//输出图片
void print_image(const pic& photo) {
    putimage(photo.x * 100, photo.y * 76, &photo.src);
}

//检查要移动到的位置是否合法
bool check(int x, int y) {
    return (0 == x && 1 == y) ||
        (0 < x && x <= 3 &&
            0 < y && y <= 3);
}

//两变量交换数值
void swap(int& a, int& b) {
    //如果a ^ b = c, 那么a = b ^ c.
    a ^= b;
    b = a ^ b;
    a = a ^ b;
    //然后a和b的值就交换了
}

//打乱
void rand_map() {
    //每次不一样
    srand(time(NULL));

    for (int i = 0; i < 2000; ++i) {
        int temp = rand() % 4;
        int tx = nowx + dx[temp];
        int ty = nowy + dy[temp];

        if (!check(tx, ty))
            continue;

        //把黑块现在的地方要移的地方的坐标交换
        swap(photo[map[nowx][nowy]].x, photo[map[tx][ty]].x);
        swap(photo[map[nowx][nowy]].y, photo[map[tx][ty]].y);
        swap(map[nowx][nowy], map[tx][ty]);

        //如果你想看怎么打乱,就取消下面注释
        //Sleep(10);
        //print_image(photo[map[nowx][nowy]]);
        //print_image(photo[map[tx][ty]]);

        nowx = tx;
        nowy = ty;
    }
}

void init() {
    initgraph(640, 640);
    setorigin(170, 206);

    //设置背景色
    setbkcolor(WHITE);
    cleardevice();

    settextcolor(BLACK);
    outtextxy(245, 415, _T("My blog : https://overisac.github.io"));

    //获取图片路径
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; '\0' != path_temp[j]; ++j) {
            path[j] = path_temp[j];
        }

        //下标i的变量获得i.jpg
        path[4] = i + '0';
        loadimage(&photo[i].src, path);

        //获得原图坐标
        if (0 == i) {
            photo[0].x = 0;
            photo[0].y = -1;
        }
        else {
            photo[i].x = (i - 1) % 3;
            photo[i].y = (i - 1) / 3;
        }
        photo[i].id = i;
    }

    nowx = 0;
    nowy = 1;

    step = 0;

    //清空
    for (int i = 0; i < 25; ++i)
        out[i] = '\0';

    print_image(photo[map[0][1]]);
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            print_image(photo[map[i][j]]);

    print_step();
    outtextxy(60, -200, _T("Please press \"Enter\" to start"));

    while (true) {
        //按键 && enter键
        while (!kbhit());

        int key_value = _getch();
        if (13 == key_value) {
            //搞不懂为什么要这么多空白字符才能清掉提示词
            outtextxy(60, -200,
                _T("                                               "));
            break;
        }
    }

    rand_map();

    print_image(photo[map[0][1]]);
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            print_image(photo[map[i][j]]);
}

//检查是否结束游戏
bool over() {
    if (0 != nowx && 1 != nowy)
        return false;

    int temp = 0;
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            if (map[i][j] != ++temp)
                return false;
    return true;
}

//返回点击了哪个图,或者没点到
int click(int x, int y) {
    for (int i = 0; i < 10; ++i)
        if (photo[i].x * 100 <= x && x < photo[i].x * 100 + 100 && photo[i].y * 76 <= y && y < photo[i].y * 76 + 76)
            return photo[i].id;
    return -1;
}

void play() {
    outtextxy(-40, -200, _T("You can choose to press \"Enter\" key to do it automatically"));
    while (true) {
        if (over()) {
            cleardevice();

            sprintf(text, "Your step is %d.", step);
            for (int i = 0; '\0' != text[i]; ++i)
                out[i] = text[i];

            outtextxy(100, 20, out);
            outtextxy(85, 40, _T("Press any key again."));
            outtextxy(60, 60, _T("Or click the cross to turn it off."));
            outtextxy(245, 415, _T("My blog : https://overisac.github.io"));

            break;
        }

        if (kbhit()) {
            int key_value = _getch();
            if (13 == key_value) {   //enter的键值是13
                void auto_play();    //不想把这函数移位置了,声明一下

                auto_play();

                outtextxy(85, 300, _T("Please press any key!"));
                outtextxy(60, 320, _T("Or click the cross to turn it off."));
                _getch();
                break;
            }
        }

        //不要定义在外面,会出问题
        MOUSEMSG mouse = GetMouseMsg();

        if (mouse.mkLButton) {
            int temp = click(mouse.x - 170, mouse.y - 206);
            if (-1 == temp)
                continue;

            for (int i = 0; i < 4; ++i) {
                int tx = nowx + dx[i];
                int ty = nowy + dy[i];

                //判断是否合法、点击的图是不是黑图的邻居
                if (check(tx, ty) && map[tx][ty] == temp) {
                    swap(photo[map[nowx][nowy]].x, photo[map[tx][ty]].x);
                    swap(photo[map[nowx][nowy]].y, photo[map[tx][ty]].y);
                    swap(map[nowx][nowy], map[tx][ty]);

                    print_image(photo[map[nowx][nowy]]);
                    print_image(photo[map[tx][ty]]);
                    nowx = tx;
                    nowy = ty;

                    ++step;
                    print_step();

                    break;
                }
            }
        }
        else {
            //据说会省点内存
            Sleep(1);
            FlushMouseMsgBuffer();
        }
    }
}

//10张图片,所以记录0-10的阶乘
int factorial[11];

//记录所有状态的下一步
int state[3628801];

//康托展开
int cantor(int arr[10]) {
    int ans = 0;
    for (int i = 0; i < 10; ++i) {
        int temp = 0;
        for (int j = i + 1; j < 10; ++j)
            if (arr[j] < arr[i])
                ++temp;
        ans += factorial[9 - i] * temp;
    }
    return ans;
}

//转成一维数组,方便康托展开
void one_dimensional(int map[4][4], int arr[10]) {
    int total = 0;
    arr[0] = map[0][1];
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            arr[++total] = map[i][j];
}

void two_dimensional(int arr[10], int map[4][4]) {
    int total = 0;
    map[0][1] = arr[0];
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            map[i][j] = arr[++total];
}

//康托逆展开(顺便找出黑色图片)
void inverse_cantor(int x, int arr[10], int map[4][4], int& nowxx, int& nowyy) {
    //太难了。。。
    int v[10];
    memset(v, 0, sizeof v);
    for (int i = 0; i < 10; ++i) {
        int cnt = x / factorial[9 - i];
        x %= factorial[9 - i];
        for (int j = 0; j < 10; j++) {
            if (v[j]) continue;
            if (!cnt) { v[j] = 1; arr[i] = j; break; }
            cnt--;
        }
    }

    two_dimensional(arr, map);

    if (0 == map[0][1]) {
        nowxx = 0;
        nowyy = 1;
        return;
    }
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            if (0 == map[i][j]) {
                nowxx = i;
                nowyy = j;
                return;
            }
}

//预处理自动玩的所有状态
void auto_init() {
    //预处理0-10的阶乘
    factorial[0] = 1;
    for (int i = 1; i < 11; ++i)
        factorial[i] = i * factorial[i - 1];

    //还没搜过的状态赋值为-1
    memset(state, -1, sizeof state);
    state[0] = 0;        //初始状态
    std::queue<int> q;
    q.push(0);

    //预处理所有状态的中间变量
    int map1[4][4], map2[4][4];
    int nowxx = nowx, nowyy = nowy;
    int arr[10], brr[10];

    while (q.size()) {
        int now = q.front();
        q.pop();
        inverse_cantor(now, arr, map1, nowxx, nowyy);

        for (int i = 0; i < 4; ++i) {
            int tx = dx[i] + nowxx;
            int ty = dy[i] + nowyy;

            if (check(tx, ty)) {
                memcpy(map2, map1, sizeof map2);

                swap(map2[nowxx][nowyy], map2[tx][ty]);
                one_dimensional(map2, brr);

                int next = cantor(brr);
                if (-1 == state[next]) { //-1代表还没搜到
                    state[next] = now;
                    q.push(next);
                }
            }
        }
    }
    state[0] = -1;
}

void auto_play() {
    int arr[10];
    one_dimensional(map, arr);

    int now = cantor(arr);        //得到当前康托展开值

    int nextx, nexty;
    while (-1 != state[now]) {
        print_step();
        ++step;

        Sleep(300);

        now = state[now];
        inverse_cantor(now, arr, map, nextx, nexty);

        swap(photo[map[nowx][nowy]].x, photo[map[nextx][nexty]].x);
        swap(photo[map[nowx][nowy]].y, photo[map[nextx][nexty]].y);

        print_image(photo[map[nowx][nowy]]);
        print_image(photo[map[nextx][nexty]]);

        nowx = nextx;
        nowy = nexty;
    }
}

int main() {
    auto_init();
    while (true) {
        init();
        play();
        //auto_play();
        _getch();
        closegraph();
    }
    return 0;
}