数字接龙-暴力

注意事项:
找到一个答案就停止深度遍历避免超时
参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
priority_queue<pr,vector<pr>,greater<pr> > q; 
const int N = 10 + 5;

int n, k;
// 8个方向的移动: 
int dy[10] = {0,1,1,1,0,-1,-1,-1};
int dx[10] = {-1,-1,0,1,1,1,0,-1};
bool vis[N][N];
int a[N][N];
vector<int> path;//记录当前的编号情况 
string ans;//最终的答案 

bool flag = false;//只要找到一个答案那么就不要在深度遍历了，我们本身就是i从小到大进行遍历的
//越往后的答案字典序就越大，因此只要找到了第一个答案就不用再往后遍历（防止有一个数据集超时） 

// 检查是否可以移动到(x,y)位置
bool check(int x, int y, int dir) {//x,y是下一个要访问的点，dir是从哪个方向去到x,y（方向数组的i值） 
    // 检查是否越界
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    
    // 检查是否已访问
    if (vis[x][y]) return false;
    
    // 对于斜向移动，检查路线是否有交叉 
    if (dir % 2 == 1) {
    	//上一个地点坐标 
        int sx = x - dx[dir];
        int sy = y - dy[dir];
        //判断路线交叉，如果 [sx + dx[dir]]和 [sx][sy + dy[dir]]已经访问过了那么就会出现路线交叉 
        if (vis[sx + dx[dir]][sy] && vis[sx][sy + dy[dir]]) {
            return false;
        }
    }
    return true;
}

// DFS搜索路径
// u是当前期望的值（0 ... k-1） 
void dfs(int x, int y, int u) {
    // 如果当前位置的值不等于期望值，返回
    if (a[x][y] != u) {
        return;
    }
    
    // 如果已经访问了所有点并到达终点
    if (path.size() == n * n - 1 && x == n - 1 && y == n - 1) {
        string t = "";
        for (int v : path) {
            t += v + '0';
        }
        ans = t;
        flag = true;//标记已经找到答案，停止深度遍历 
        return;
    }
    
    // 尝试8个方向的移动
    for (int i = 0; i < 8; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (check(tx, ty, i)) {//检查下一个点是否合理 
            vis[tx][ty] = 1;//标记访问 
            path.push_back(i);//加入编号集 
            dfs(tx, ty, (u + 1) % k);//深度遍历 
            path.pop_back();//深度遍历结束 恢复原来状态 
            vis[tx][ty] = 0;//深度遍历结束 恢复原来状态 
            if(flag) return;//已经找到答案，停止深度遍历 
        }
    }
}

int main() {
    // 初始化访问数组
    memset(vis, 0, sizeof(vis));
    
    // 读取输入
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    
    // 标记起点为已访问
    vis[0][0] = 1;
    
    // 从起点开始DFS
    dfs(0, 0, 0);
    
    // 输出结果
    if (!ans.empty()) {
        cout << ans;
    } else {
        cout << "-1";
    }
    
    return 0;
}