涟源网络建站,ppt哪个网站做的好,廊坊优化外包,做一个网站首页多少钱题意#xff1a;经过所有格子#xff0c;并且不能进行交叉#xff0c;走的下一个格子必须是当前格子值1%k#xff0c;输出路径最小的那一条#xff08;有8个方向#xff0c;一会粘图#xff09;
思路#xff1a;按照8个方向设置偏移量进行dfs#xff0c;第一个到达终…题意经过所有格子并且不能进行交叉走的下一个格子必须是当前格子值1%k输出路径最小的那一条有8个方向一会粘图
思路按照8个方向设置偏移量进行dfs第一个到达终点的即为最小路径直接输出即可
代码
#includebits/stdc.h
using namespace std;
#define N 12int 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];
vectorint path;void dfs(int u,int v,int st){if(f)return;if(unvnstn*n-1){for(auto it:path)coutit;coutendl;ftrue;return;}for(int i0;i8;i){int xxux[i];int yyvy[i];if(xx1||xxn||yy1||yyn)continue;if(vis[xx][yy])continue;if(g[xx][yy]!(st1)%k)continue;if(i%2)if(vis[ux[(i-1)%8]][vy[(i-1)%8]]vis[ux[(i1)%8]][vy[(i1)%8]])continue;vis[xx][yy]true;path.push_back(i);dfs(xx,yy,st1);vis[xx][yy]false;path.pop_back();}
}int main(){cinnk;for(int i1;in;i)for(int j1;jn;j)cing[i][j];vis[1][1]true;dfs(1,1,0);if(!f)cout-1endl;return 0;
}/*
3 3
0 2 0
1 1 1
2 0 29 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 810 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 010 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
