#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
//#include <termio.h>
#include <conio.h> 
#include <iomanip>
#include<windows.h>
#define clear() system("cls")
using namespace std;

int num[10][10];
int rd, tme;
bool validMove;

//int getch() // 不回显函数
//{
//    struct termios nts, ots;
//    // 得到当前终端(0表示标准输入)的设置
//    if (tcgetattr(0, &ots) < 0) return EOF;
//    // 设置终端为Raw原始模式，该模式下所有的输入数据以字节为单位被处理
//    nts = ots;
//    cfmakeraw(&nts); 
//    // 设置上更改之后的设置
//    if (tcsetattr(0, TCSANOW, &nts) < 0) return EOF;
//    // 设置还原成老的模式
//    int cr;
//    cr = getchar();
//    if (tcsetattr(0, TCSANOW, &ots) < 0)  return EOF;
//    return cr;
//}

void intro() // 游戏规则展示
{
    cout << "***********************************************************" << endl;
    cout << "欢迎来到 数字华容道 游戏～" << endl;
    cout << "在这个游戏里会有一个 4*4 的表格，每个网格中有一个1~15之间的数" << endl;
    cout << "可以选择 w、s、a、d，上下左右的滑动，移动数" << endl;
    cout << "当按大小顺序从左到右、从上到下排列好所有的数，游戏结束！" << endl; 
    cout << "点击【ENTER】开始游戏" << endl;
    cout << "点击【ESC】退出游戏" << endl;
    cout << "***********************************************************" << endl;
}

void init() // 初始化网格
{
    int a[20] = {};
    for (int i = 1; i <= 15; i++)
    {
        a[i] = i;
    }
    srand(time(0));
    random_shuffle(a + 1, a + 15 + 1);
    int cnt = 0;
    for (int i = 1; i <= 15; i++)
    {
        for (int j = i+1; j <= 15; j++)
        {
            if (a[i] > a[j]) // 逆序数对个数
            {
                cnt++;
            }
        }
    }
    if (cnt % 2 == 1) // 逆序数对为奇数无解，减少一个
    {
        for (int i = 1; i <= 15; i++)
        {
            bool jump = false;
            for (int j = i+1; j <= 15; j++)
            {
                if (a[i] > a[i+1])
                {
                    swap(a[i], a[i+1]);
                    jump = true;
                    break;
                }
            }
            if (jump) break;
        }
    }
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            num[i][j] = a[(i-1)*4+j];
        }
    }
}

void drawBoard() // 打印当前表格
{
    // 输出上边框
    cout << "  ╔";
    for (int i = 1; i <= 4 - 1; i++) cout << "════╤";
    cout << "════╗\n";
    // 输出中间部分
    for (int i = 1; i <= 4; i++) // 行
    {
        cout << "  ║";
        for (int j = 1; j <= 4; j++) // 列
        {
            if (num[i][j] >= 10)
                cout << " " << num[i][j] << " "; 
            else if (num[i][j] != 0)
                cout << "  " << num[i][j] << " ";
            else
                cout << "    ";
            if (j != 4)
                cout << "│";
            else
                cout << "║";
        }
        cout << " \n";
        // 输出下边框
        if (i != 4)
        {
            cout << "  ╟";
            for (int i = 1; i <= 4 - 1; i++) cout << "────┼";
            cout << "────╢\n";
        }
        else
        {
            cout << "  ╚";
            for (int i = 1; i <= 4 - 1; i++) cout << "════╧";
            cout << "════╝\n";
        }
    }
}

bool gameOver()
{
    int a[20];
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            a[(i-1)*4+j] = num[i][j];
        }
    }
    for (int i = 1; i <= 15; i++)
    {
        if (a[i] != i)
        {
            return false;
        }
    }
    return true;
}

void MoveUp() // 向上移动
{   
    int x, y;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            if (num[i][j] == 0)
            {
                x = i;
                y = j;
            }
        }
    }
    if (x == 4) validMove = false;
    else
    {
        validMove = true;
        swap(num[x][y], num[x+1][y]);
    }
}

void MoveDown() // 向下移动
{   
    int x, y;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            if (num[i][j] == 0)
            {
                x = i;
                y = j;
            }
        }
    }
    if (x == 1) validMove = false;
    else
    {
        validMove = true;
        swap(num[x][y], num[x-1][y]);
    }
}

void MoveLeft() // 向左移动
{   
    int x, y;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            if (num[i][j] == 0)
            {
                x = i;
                y = j;
            }
        }
    }
    if (y == 4) validMove = false;
    else
    {
        validMove = true;
        swap(num[x][y], num[x][y+1]);
    }
}

void MoveRight() // 向右移动
{   
    int x, y;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            if (num[i][j] == 0)
            {
                x = i;
                y = j;
            }
        }
    }
    if (y == 1) validMove = false;
    else
    {
        validMove = true;
        swap(num[x][y], num[x][y-1]);
    }
}

void Win() // 玩家获胜
{
    cout << "**********************************" << endl;
    cout << "——————————— ROUND:" << rd << " ————————————" << endl;
    cout << "——————————— TIME:" << tme << " s———————————" << endl;
    cout << "——————————— 玩家获胜！ ————————————" << endl;
    cout << "**********************************" << endl << endl;
    exit(0);
}

void game() // 开始游戏
{
    system("cls");
    cout << "**********************************" << endl;
    cout << "—————————— Ready Go～ ————————————" << endl;
    cout << "**********************************" << endl;
    drawBoard(); // 打印棋盘
    
    char ch = 0;
    int sta = time(0);
    while (!gameOver()) // 当游戏没结束时
    {
        tme = time(0) - sta;
        // 按键 操作数 时间
        cout << "Key:" << ch << " Round:" << rd << " Time:" << tme << endl;
        cout << "Tips：" << endl;
        cout << "w —— 上移" << endl;
        cout << "s —— 下移" << endl;
        cout << "a —— 左移" << endl;
        cout << "d —— 右移" << endl;
        cout << "e —— 退出游戏" << endl;
        cout << "r —— 开始新游戏" << endl;
        cout << "选择以上指令！" << endl;
        
        ch = getch(); // 输入操作指令
        if (ch == 'w') MoveUp();
        else if (ch == 's') MoveDown();
        else if (ch == 'a') MoveLeft();
        else if (ch == 'd') MoveRight();
        else if (ch == 'e') exit(0);
        else if (ch == 'r') // 开始新游戏
        {
            sta = time(0); // 清空开始时间
            rd = 0; // 清空操作次数
            memset(num, 0, sizeof(num)); // 清空表格数据
            return; 
        }
        else
        {
            cout << endl << "———————输入有误，请重新输入指令！———————" << endl << endl;
            continue;
        }
        system("cls");
        drawBoard(); // 打印棋盘
        if (validMove) rd++; // 记录操作次数
    }
    Win();
}

int main()
{
    while (true)
    {
        intro(); // 游戏规则展示
        char ch = getch(); // 不回显函数，当用户按下某个字符时，函数自动读取，无需按回车
        if (ch == 13) // CR回车的ascii是13
        {
            init(); //初始化方格数据
            game(); // 开始游戏
        }
        else if (ch == 27) // ESC的ascii是27
        {
            cout << "退出游戏！" << endl;
            break;
        }
        else  cout << "输入有误，请再次输入！" << endl;
    }
    return 0;
}