数字接龙 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 20;
int n, k;
bool flag;
int num[maxn][maxn], ans[maxn * maxn];
bool vis[maxn][maxn], crossVis[maxn][maxn][maxn][maxn];
const int dir[8][2] = {
    {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}
};

bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool cross(int x, int y, int idx) {
    int x1 = x + dir[(idx + 1) % 8][0];
    int y1 = y + dir[(idx + 1) % 8][1];
    int x2 = x + dir[(idx + 7) % 8][0];
    int y2 = y + dir[(idx + 7) % 8][1];
    return in(x1, y1) && in(x2, y2) && (crossVis[x1][y1][x2][y2] || crossVis[x2][y2][x1][y1]);
}

void dfs(int x, int y, int kk, int depth) {
    if (depth == n * n - 1) {
        if (x == n - 1 && y == n - 1) {
            flag = true;
            for (int i = 0; i < depth; ++i) {
                cout << ans[i];
            }
            cout << endl;
        }
        return ;
    }
    for (int i = 0; i < 8; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (in(xx, yy) && !vis[xx][yy] && num[xx][yy] == kk) {
            if (i % 2 == 1 && cross(x, y, i)) {
                continue;
            }
            ans[depth] = i;
            vis[xx][yy] = true;
            crossVis[x][y][xx][yy] = true;
            dfs(xx, yy, (kk + 1) % k, depth + 1);
            vis[xx][yy] = false;
            crossVis[x][y][xx][yy] = false;
            if (flag) {
                return ;
            }
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> num[i][j];
        }
    }
    vis[0][0] = true;
    dfs(0, 0, 1 % k, 0);
    if (!flag) {
        cout << -1 << endl;
    }

    return 0;
}