#include <bits/stdc++.h>

using namespace std;

// 蛇形矩阵
// https://blog.csdn.net/weixin_45907018/article/details/104039165
void snakeMatrix() {
    int n = 8, i, j, x = 1;
    int a[10][10] = {0};

    //对于每一条左下->右上的斜线,从左上到右下依次编号为1,2,3,...,2n-1,之所以为2n-1，是因为中间那条是重复的
    for (i = 0; i < 2 * n - 1; i++) {
        //本条线，画几个数
        for (j = i; j >= 0; j--) {
            //越界检查
            if (j < n & i - j < n) {
                if (i % 2 > 0) //奇数
                    a[i - j][j] = x++;     //左下到右上
                else
                    a[j][i - j] = x++;     //右上到左下
            }
        }
    }
    //输出结果
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            cout << setw(2) << a[i][j] << " ";
        cout << endl;
    }
}

//*************************************************************************
/*
 思路：
（1）到矩阵的边缘需要转向，转向的方向是数组的下一个内容，如果越界，就是位置0
（2）如果前面要走的位置已经走过了，就需要转向。上下左右独立封装成函数，用于控制x,y的加加减减。
（3）如果尝试四次还没有找到出路，标识进入死循环，程序终止。
*/
// 上：1，下2：左：3：右：4
const int UP = 1, DOWN = 2, LEFT = 3, RIGHT = 4;
//顺时针
int dirSun[4] = {RIGHT, DOWN, LEFT, UP};
//逆时针
int dirNi[4] = {RIGHT, UP, LEFT, DOWN};
//矩阵
int a[10][10] = {0};
//假设矩阵为8*8
int n = 5;
//开始点
int x = 4, y = 0;
//开始时的方向
int dir = RIGHT;
//第一个位置标识上
int step = 1;

//向上走一步
bool UpStep() {
    if (x - 1 >= 0 && a[x - 1][y] == 0) {
        a[--x][y] = ++step;
        return true;
    }
    return false;
}
//向下走一步
bool DownStep() {
    if (x + 1 < n && a[x + 1][y] == 0) {
        a[++x][y] = ++step;
        return true;
    }
    return false;
}
//向右走一步
bool RightStep() {
    if (y + 1 < n && a[x][y + 1] == 0) {
        a[x][++y] = ++step;
        return true;
    }
    return false;
}
//向左走一步
bool LeftStep() {
    if (y - 1 >= 0 && a[x][y - 1] == 0) {
        a[x][--y] = ++step;
        return true;
    }
    return false;
}

//获取下一个需要尝试的方向
int NextDir(int turn) {
    //需要分别讨论顺时针还是逆时针，因为数组的数组是不同的
    if (turn == 1) { //顺时针
        for (int i = 0; i < 4; ++i) {
            if (dirSun[i] == dir) {
                return dirSun[i + 1 == 4 ? 0 : i + 1];
            }
        }
    } else { //逆时针
        for (int i = 0; i < 4; ++i) {
            if (dirNi[i] == dir) {
                return dirNi[i + 1 == 4 ? 0 : i + 1];
            }
        }
    }
    return -1;
}

//人工智能走一步，也是核心的思路
bool autoStep(int turn) { //turn:是顺时针:1,还是逆时针:2
    bool success = false;
    int tryCount = 0;
    while (tryCount < 4) {
        //1、获取当前方向,决定向哪个方向走一步
        switch (dir) {
            case UP:
                success = UpStep();
                if (success) return true;
                //换方向
                dir = NextDir(turn);
                break;
            case DOWN:
                success = DownStep();
                if (success) return true;
                //换方向
                dir = NextDir(turn);
                break;
            case RIGHT:
                success = RightStep();
                if (success) return true;
                //换方向
                dir = NextDir(turn);
                break;
            case LEFT:
                success = LeftStep();
                if (success) return true;
                //换方向
                dir = NextDir(turn);
                break;
        }
        tryCount++;
    }
    return false;
}

void helixMatrix() {
    //出发点记录为第一步
    a[x][y] = 1;
    //共执行n*n次，即填充满为止。
    while (step < n * n) {
        //模拟顺时针
        bool success = autoStep(2);
        if (!success) {
            cout << "无法走到最后，请检查逻辑是否不正确！" << endl;
            break;
        }
    }

    //输出二维矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << setw(2) << a[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    //蛇形矩阵
    snakeMatrix();
    //螺旋矩阵
    helixMatrix();
    return 0;
}