由于蓝桥杯临近，博主想刷点题来充实自己，话不多少，看题。

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为N × N 的格子棋盘上展开，其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下：

1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N − 1, N − 1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。

3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。

4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 所示；因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示，如下图 1是一个迷宫示例，它所对应的答案就是：41255214。

蓝桥杯2024年第十五届省赛真题-数字接龙

现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

显然题目是用DFS+剪枝，重点在于处理交叉的情况，由于数据量挺小，博主就开了一个四位数组存储。

c++代码

#include
#include
#include
using namespace std;
vectors;//获取到的数组情况
vector>num1;//获取后按字典顺序存放
int dx[] = { 0,1,1,1,0,-1,-1,-1 };//x方向
int dy[] = { 1,1,0,-1,-1,-1,0,1 };//y方向
int n, k;
int num = 0;
int arr[11][11] = { -1 };//记录数组
int arr1[11][11] = { -1 };//记录访问情况
int arr2[11][11][11][11] = { -1 };//记录交叉情况
void dfs(int x, int y) {
    arr1[x][y] = 0;
    if (x == n && y == n) {
        if (s.size() == n)
            for (int i = 0; i < s.size();i++) {
                cout << s[i];
            }
            num1.push_back(s);
    }
    else {
        if (num == k - 1)num = -1;
        else {
            for (int i = 0; i < 8; i++) {//遍历8个方向
                if (arr1[x + dx[i]][y + dx[i]] == 0)continue;
                if (arr[x + dx[i]][y + dx[i]] != num + 1)continue;
                if (i == 1 && arr2[x][y - 1][x + dx[i] + 1][y + dy[i]] == 1)continue;
                if (i == 3 && arr2[x + 1][y][x + dx[i] - 1][y + dy[i]] == 1)continue;
                if (i == 5 && arr2[x][y - 1][x + dx[i]][y + dy[i] + 1] == 1)continue;
                if (i == 7 && arr2[x - 1][y][x + dx[i]][y + dy[i] - 1] == 1)continue;
                s.push_back(i);
                arr2[x + dx[i]][y + dy[i]][x][y] = 1;
                arr2[x][y][x + dx[i]][y + dy[i]] = 1;
                num++;
                dfs(x + dx[i], y + dx[i]);
                num--;
                arr2[x][y][x + dx[i]][y + dy[i]] = -1;
                arr2[x + dx[i]][y + dy[i]][x][y] = -1;
                arr1[x][y] = -1;
                s.pop_back();
            }
        }
    }
}
int main()
{
    cin >> n >> k;
    for (int i= 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    return 0;
}