```cpp #include <iostream> #include <vector> #include <set> #include <string> using namespace std; using ll = long long; // [y][x] constexpr int fx[8][2] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; int n = 0, k = 0; vector<vector<int>> tizu; vector<vector<int>> vis; set<string> res; string now; int sb[10][10][10][10]; void dfs(int i, int j, int next) { if (i == n - 1 && j == n - 1) { if ((int)now.size() == n * n - 1) { // res.insert(now); cout << now << '\n'; exit(0); } return; } next = (next + 1) % k; for (int d = 0; d < 8; ++d) { char c = '0' + d; int y = i + fx[d][0], x = j + fx[d][1]; if (y < 0 || y >= n || x < 0 || x >= n || vis[y][x] || tizu[y][x] != next) { continue; } // [i][j] -> [y][x] if (c == '1' && (sb[y+1][x][y][x-1] || sb[y][x-1][y+1][x])) continue; if (c == '3' && (sb[y-1][x][y][x-1] || sb[y][x-1][y-1][x])) continue; if (c == '5' && (sb[y-1][x][y][x+1] || sb[y][x+1][y-1][x])) continue; if (c == '7' && (sb[y+1][x][y][x+1] || sb[y][x+1][y+1][x])) continue; vis[y][x] = 1; sb[i][j][y][x] = 1; now += c; dfs(y, x, next); now.pop_back(); sb[i][j][y][x] = 0; vis[y][x] = 0; } } int main() { cin >> n >> k; tizu = vector<vector<int>>(n, vector<int>(n)); vis = vector<vector<int>>(n, vector<int>(n)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> tizu[i][j]; vis[0][0] = 1; if (tizu[0][0] == 0) dfs(0, 0, 0); cout << "-1\n"; return 0; } ```

``` #include <bits/stdc++.h> using namespace std; #define N 12 //输入 int n, k; //起点终点 int qx = 0, qy = 0, zx, zy; //地图 int g[N][N]; //标记没标记过 int f[N][N]; //这个点走的方向 int fx[N][N]; //记录方向用的 int bu[N * N]; //方向 int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; //有没有结果 int res = 0; //输出 void otto() { for (int i = 0; i < n * n - 1; ++i) cout << bu[i]; } //搜索 void dfs(int x, int y, int bus, int zt) { //已经找到结果了，不找了 if (res == 1) return; //坐标正确，步数正确，允许输出 if (x == zx && y == zy && bus == n * n - 1) { //标记为找到 res = 1; //调用函数把结果打出来 otto(); return; } //循环走方格 if (zt == k - 1) zt = -1; //八个方向，顺时针就不用管字典序 for (int i = 0; i < 8; ++i) { //一个新的点的俩坐标 int vx = x + dx[i]; int vy = y + dy[i]; //标记 错号 出界 if (f[vx][vy] || g[vx][vy] != zt + 1 || x < 0 || y < 0 || x >= n || y >= n) continue; //如果会交叉 if (i == 1 && (fx[x][y + 1] == 7 || fx[x - 1][y] == 3)) continue; if (i == 3 && (fx[x][y + 1] == 5 || fx[x + 1][y] == 1)) continue; if (i == 5 && (fx[x][y - 1] == 3 || fx[x + 1][y] == 7)) continue; if (i == 7 && (fx[x][y - 1] == 1 || fx[x - 1][y] == 5)) continue; //开搜 f[vx][vy] = 1; fx[x][y] = i; bu[bus] = i; dfs(vx, vy, bus + 1, g[vx][vy]); bu[bus] = -1; fx[x][y] = -1; f[vx][vy] = 0; } } int main() { //输入 cin >> n >> k; zx = n - 1, zy = n - 1; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> g[i][j]; //初始化一些数据 memset(fx, -1, sizeof fx); memset(f, 0, sizeof f); memset(bu, -1, sizeof bu); //起点标成走过 f[qx][qy] = 1; //我搜搜搜 dfs(qx, qy, 0, 0); //没找到 if (!res) cout << -1 << endl; return 0; } ```

```cpp #include <bits/stdc++.h> using namespace std; int n, k, now = 1, res; int a[15][15], m[15][15], r[105], s[15][15]; // 棋盘，访问标记，路径方向，路径次序 int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; bool check(int xx, int yy, int dir) { // 判断是否交叉 if (dir % 2 == 0) return false; // 如果方向是上，下，左，右就不用判断了 switch (dir) { case 1: return s[xx - 1][yy] != -1 && s[xx][yy + 1] != -1 && abs(s[xx - 1][yy] - s[xx][yy + 1]) == 1; case 3: return s[xx + 1][yy] != -1 && s[xx][yy + 1] != -1 && abs(s[xx + 1][yy] - s[xx][yy + 1]) == 1; case 5: return s[xx + 1][yy] != -1 && s[xx][yy - 1] != -1 && abs(s[xx + 1][yy] - s[xx][yy - 1]) == 1; case 7: return s[xx - 1][yy] != -1 && s[xx][yy - 1] != -1 && abs(s[xx - 1][yy] - s[xx][yy - 1]) == 1; } } void dfs(int x, int y) { if (res == 1) return; // 有结果了直接返回 if (x == n && y == n) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (m[i][j] == 0) return; } } res = 1; for (int i = 1; i <= n * n - 1; i++) { // 输出并结束 cout << r[i]; } exit(0); } for (int i = 0; i < 8; i++) { int tx = x + dx[i], ty = y + dy[i]; if (tx < 1 || tx > n || ty < 1 || ty > n) continue; // 越界检查 if (((a[x][y] + 1) % k) != a[tx][ty]) continue; // 数字序列检查 if (m[tx][ty]) continue; // 访问标记检查 if (check(x, y, i)) continue; // 交叉检查 m[tx][ty] = 1; // 标记 r[now] = i; s[tx][ty] = now; now++; dfs(tx, ty); now--; // 回溯 s[tx][ty] = -1; m[tx][ty] = 0; } } int main() { memset(s, -1, sizeof(s)); cin >> n >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } if (a[1][1] != 0) { // 如果起点不是0，直接结束 cout << "-1"; return 0; } m[1][1] = 1; // 从(1,1)开始 s[1][1] = 0; // 为了用now变量记录，下标从0开始 dfs(1, 1); // 开搜！ cout << "-1"; // 如果没有符合的 return 0; } ```

``` #include<iostream> #include<vector> #include<algorithm> using namespace std; int path_x[8] = { 0,1,1,1,0,-1,-1,-1 }; int path_y[8] = { -1,-1,0,1,1,1,0,-1 }; int N, K; int flag = false; vector<int> ans;//记录最终答案 void solve(vector<vector<int>>& maps, int cur_x, int cur_y, vector<int>& Temp, int pos, vector<vector<bool>>& vis, int dep, vector<vector<int>>& dire) { if (pos == K - 1)pos = -1;//如果已经走完了1到K-1，则重新开始轮回 if (cur_x == N - 1 && cur_y == N - 1)//走到底端了，进行判断 { if (dep != N * N)return;//未全部走遍 ans = Temp; flag = true; return; } for (int i = 0; i < 8; i++)//路径试探 { int new_x = cur_x + path_x[i];//新地址x坐标 int new_y = cur_y + path_y[i];//新地y坐标 if (new_x > N - 1 || new_x < 0 || new_y > N - 1 || new_y < 0)continue;//新坐标是否在合法地图内 if (vis[new_y][new_x])continue;//已经走过则不走 if (i == 1 && (dire[cur_y - 1][cur_x] == 3 || dire[cur_y][cur_x + 1] == 7)) continue;//判路径不交叉 if (i == 3 && (dire[cur_y + 1][cur_x] == 1 || dire[cur_y][cur_x + 1] == 5)) continue;//判路径不交叉 if (i == 5 && (dire[cur_y + 1][cur_x] == 7 || dire[cur_y][cur_x - 1] == 3)) continue;//判路径不交叉 if (i == 7 && (dire[cur_y - 1][cur_x] == 5 || dire[cur_y][cur_x - 1] == 1)) continue;//判路径不交叉 if (maps[new_y][new_x] != pos + 1)continue;//符合路径规则 vis[new_y][new_x] = 1;//记录新点，已经走 Temp.push_back(i);//插入可能坐标 dire[cur_y][cur_x] = i; solve(maps, new_x, new_y, Temp, pos + 1, vis, dep + 1, dire);//递归 if (flag)return;//剪枝 Temp.pop_back();//回溯 vis[new_y][new_x] = 0;//回溯 dire[cur_y][cur_x] = -1; } } int main() { cin >> N >> K; vector<vector<int>> maps(N);//记录地图 vector<vector<bool>> vis(N);//记录地图有无被走过 vector<vector<int>> dire(N);//记录地图有无被走过 for (int i = 0; i < N; i++)//初始化地图 { maps[i].resize(N); vis[i].resize(N); dire[i].resize(N); for (int j = 0; j < N; j++) { cin >> maps[i][j]; vis[i][j] = 0; dire[i][j] = -1; } } vector<int> Temp;//记录有效路径 Temp.reserve(N * N - 1); ans.reserve(N * N - 1); vis[0][0] = 1; solve(maps, 0, 0, Temp, 0, vis, 1, dire); for (auto e : ans) { cout << e; } if (ans.empty()) { cout << -1; } return 0; } ```