#include <iostream>
#include <string.h>

#define BORDSIZE 4
#define SIZE 16

using namespace std;

void printMap(int arr16[SIZE])
{
    int(*arr2v)[BORDSIZE] = (int(*)[BORDSIZE])arr16;
    for (int i = 0; i < BORDSIZE; i++)
    {
        for (int j = 0; j < BORDSIZE; j++)
        {
            cout << arr2v[i][j] << " ";
        }
        cout << endl;
    }
    cout << "-----------------" << endl;
}

int findFirstNotZero(const int curX, const int curY, int operX, int operY, int *arr16, int &outX, int &outY)
{
    int(*arr2v)[BORDSIZE] = (int(*)[BORDSIZE])arr16;
    outX = curX;
    outY = curY;
    if (outX < 0 || outY < 0 || outX >= BORDSIZE || outY >= BORDSIZE)
    {
        return -1;
    }
    while (outX >= 0 && outY >= 0 && outX < BORDSIZE && outY < BORDSIZE)
    {
        if (arr2v[outX][outY] != 0)
        {
            return 0;
        }
        outX += operX;
        outY += operY;
    }
    return -1;
}

int MoveTo(const int *arr16, int operX, int operY, int *arr16Out, int maxLevel, bool &bMaxLevelHappen)
{
    memcpy(arr16Out, arr16, sizeof(int) * SIZE);
    int(*arr2v)[BORDSIZE] = (int(*)[BORDSIZE])arr16Out;
    int score = 0;
    bMaxLevelHappen = false;
    for (int idx1 = 0; idx1 < BORDSIZE; idx1++)
    {
        int curX = 0, curY = 0;
        if (operX == 0)
        {
            curX = idx1;
            if (operY == 1)
            {
                curY = 0;
            }
            else if (operY == -1)
            {
                curY = BORDSIZE - 1;
            }
            else
            {
                return -1;
            }
        }
        else if (operY == 0)
        {
            curY = idx1;
            if (operX == 1)
            {
                curX = 0;
            }
            else if (operX == -1)
            {
                curX = BORDSIZE - 1;
            }
            else
            {
                return -1;
            }
        }
        else
        {
            return -1;
        }

        while (curX >= 0 && curX < BORDSIZE && curY >= 0 && curY < BORDSIZE)
        {
            int findedFirstNotZeroX = 0, findedFirstNotZeroY = 0;
            // 从(curX,curY)开始在oper方向上用offset偏移寻找第一个非零放到(curX,curY)，并把移动的元素位置赋为0
            int iRet = findFirstNotZero(curX, curY, operX, operY, arr16Out, findedFirstNotZeroX, findedFirstNotZeroY);
            if (iRet != 0)
            {
                break;
            }
            cout << "find not zero:" << arr2v[findedFirstNotZeroX][findedFirstNotZeroY] << endl;
            arr2v[curX][curY] = arr2v[findedFirstNotZeroX][findedFirstNotZeroY];
            if (findedFirstNotZeroX != curX || findedFirstNotZeroY != curY)
            {
                arr2v[findedFirstNotZeroX][findedFirstNotZeroY] = 0;
            }

            cout << "idx1:" << idx1 << endl;
            printMap(arr16Out);
            // 从(curX,curY)+(operX,operY)开始在oper方向上用offset偏移寻找第一个非零放到(curX,curY)+(operX,operY)，并把移动的元素位置赋为0
            iRet = findFirstNotZero(curX + operX, curY + operY, operX, operY, arr16Out, findedFirstNotZeroX, findedFirstNotZeroY);
            if (iRet != 0)
            {
                break;
            }
            cout << "find not zero:" << arr2v[findedFirstNotZeroX][findedFirstNotZeroY] << endl;
            arr2v[curX + operX][curY + operY] = arr2v[findedFirstNotZeroX][findedFirstNotZeroY];
            if (findedFirstNotZeroX != curX + operX || findedFirstNotZeroY != curY + operY)
            {
                arr2v[findedFirstNotZeroX][findedFirstNotZeroY] = 0;
            }
            cout << "idx1:" << idx1 << endl;
            printMap(arr16Out);
            // 尝试(curX,curY)与(curX,curY)+(operX,operY)的合并
            if (arr2v[curX][curY] == arr2v[curX + operX][curY + operY] && arr2v[curX][curY] < maxLevel)
            {
                arr2v[curX][curY] *= 2;
                if (arr2v[curX][curY] == maxLevel)
                {
                    bMaxLevelHappen = true;
                }
                score += arr2v[curX][curY];
                arr2v[curX + operX][curY + operY] = 0;
            }
            cout << "idx1:" << idx1 << " try merge" << endl;
            printMap(arr16Out);
            //  偏移到下一个位置，进行下一次Loop
            curX += operX;
            curY += operY;
        }
    }
    return score;
}

bool gameOver(const int *arr16, int maxLevel)
{
    // 判断棋盘有没有满
    for (int i = 0; i < SIZE; i++)
    {
        if (arr16[i] == 0)
        {
            return false;
        }
    }
    int arr16Out[SIZE] = {0};
    bool bMaxLevelHappen = false;
    // 向上探测
    int score = MoveTo(arr16, 1, 0, arr16Out, maxLevel, bMaxLevelHappen);
    if (score != 0)
    {
        return false;
    }
    // 向下探测
    score = MoveTo(arr16, -1, 0, arr16Out, maxLevel, bMaxLevelHappen);
    if (score != 0)
    {
        return false;
    }
    // 向左探测
    score = MoveTo(arr16, 0, 1, arr16Out, maxLevel, bMaxLevelHappen);
    if (score != 0)
    {
        return false;
    }
    // 向右探测
    score = MoveTo(arr16, 0, -1, arr16Out, maxLevel, bMaxLevelHappen);
    if (score != 0)
    {
        return false;
    }
    return true;
}

enum Move
{
    TOP = 0, //(1,0)
    DOWN,    //(-1,0)
    LEFT,    //(0,1)
    RIGHT    //(0,-1)
};

int main()
{
    int maxLevel = 12;
    int arr16[SIZE] = {1, 2, 3, 4,
                       2, 3, 4, 5,
                       3, 4, 5, 6,
                       4, 5, 6, 7};
    printMap(arr16);
    cout << "start" << endl;
    bool bMaxLevelHappen = false;
    int arr16Out[SIZE] = {0};
    int score = MoveTo(arr16, 0, -1, arr16Out, maxLevel, bMaxLevelHappen);
    printMap(arr16);
    printMap(arr16Out);
    cout << "score:" << score << endl;
    cout << "maxHappen:" << bMaxLevelHappen << endl;
    cout << "game over:" << gameOver(arr16Out, maxLevel) << endl;
    return 0;
}