解题思路:基本搜索，
注意事项:一定注意细节，字典序最小。
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int dx[]={-1,-1,0,1,1,1,0,-1};//搜索常用，遍历八个方向
int dy[]={0,1,1,1,0,-1,-1,-1};
int k,n;
bool ac=false;//非常重要，用来解决字典需最小
vector<int> now,res;存下标，可以字符串，但是我用了一直出问题就很烦
int e[N][N];//地图
bool st[N][N];//记录是否走过
void dfs(int x,int y,int cnt){
if (ac) return ;
if (x == n && y == n && now.size() == (n * n - 1)) {//这里重点，找到一次就可以输出了
ac = true;
res = now;
return ;
}
int nxp = cnt % k;
for(int i=0;i<8;++i){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>n||st[nx][ny]) continue;//不符合的条件出界和已经访问过
if(e[nx][ny]!=nxp) continue;//当前走的位置不符合地图上的数字
if(i==1&&st[x-1][y]==1&&st[x][y+1]==1) continue;
if(i==3&&st[x+1][y]==1&&st[x][y+1]==1) continue;
if(i==5&&st[x+1][y]==1&&st[x][y-1]==1) continue;
if(i==7&&st[x-1][y]==1&&st[x][y-1]==1) continue;
st[nx][ny]=true;//标记
now.push_back(i);放入
dfs(nx,ny,cnt+1);搜下一个
now.pop_back();不符合的放出
st[nx][ny]=false;回溯
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin>>e[i][j];
}
}
st[1][1]=true;//
dfs(1,1,1);
if(res.size()==0) cout<<-1<<endl;
else{
for(int i=0;i<res.size();++i) cout<<res[i];
cout<<endl;
}
return 0;
}
0.0分
4 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
以下是改良后的部分代码片段 // 新增：用于记录路径交叉状态的数组 bool crossVis[N][N][N][N]; // 判断路径是否交叉的函数 bool cross(int x, int y, int idx) { int x1 = x + dx[(idx + 1) % 8]; int y1 = y + dy[(idx + 1) % 8]; int x2 = x + dx[(idx + 7) % 8]; int y2 = y + dy[(idx + 7) % 8]; return (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= n && x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= n && (crossVis[x1][y1][x2][y2] || crossVis[x2][y2][x1][y1])); } // 新增：调用交叉判断函数 if (cross(x, y, i)) continue; st[nx][ny] = true; now.push_back(i); crossVis[x][y][nx][ny] = true; dfs(nx, ny, cnt + 1); now.pop_back(); st[nx][ny] = false; crossVis[x][y][nx][ny] = false;