题意：经过所有格子，并且不能进行交叉，走的下一个格子必须是当前格子值+1%k，输出路径最小的那一条（有8个方向，一会粘图）
思路：按照8个方向设置偏移量进行dfs，第一个到达终点的即为最小路径，直接输出即可
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 12
int n,k;
int g[N][N];
int x[]={-1,-1,0,1,1,1,0,-1};
int y[]={0,1,1,1,0,-1,-1,-1};
bool f,vis[N][N];
vector<int> path;
void dfs(int u,int v,int st){
if(f)return;
if(u==n&&v==n&&st==n*n-1){
for(auto it:path)cout<<it;cout<<endl;
f=true;
return;
}
for(int i=0;i<8;i++){
int xx=u+x[i];
int yy=v+y[i];
if(xx<1||xx>n||yy<1||yy>n)continue;
if(vis[xx][yy])continue;
if(g[xx][yy]!=(st+1)%k)continue;
if(i%2)if(vis[u+x[(i-1)%8]][v+y[(i-1)%8]]&&vis[u+x[(i+1)%8]][v+y[(i+1)%8]])continue;
vis[xx][yy]=true;
path.push_back(i);
dfs(xx,yy,st+1);
vis[xx][yy]=false;
path.pop_back();
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>g[i][j];
vis[1][1]=true;
dfs(1,1,0);
if(!f)cout<<-1<<endl;
return 0;
}
/*
3 3
0 2 0
1 1 1
2 0 2
9 9
0 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8
10 10
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 9
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
10 10
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
这组样例还是过不了！！！
10 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
*/最后提一嘴：
这个爬山题也太难了吧，2 1 1 48 49这种样例咋做啊！！！期待官方std