数字接龙（dfs）（蓝桥杯）

非常好的联系dfs的一道题目！
推荐看这位大佬的详解——>大佬详细题解

#include #include #include #include using namespace std;const int N = 2e5 + 10,M=20;int a[M][M];bool val[M][M];int dx[]={-1,-1,0,1,1,1,0,-1};int dy[]={0,1,1,1,0,-1,-1,-1};int n,k;int path[M][M];string ans; //这时的数字 //答案字符 //总共经过数目void dfs(int x,int y,int url,string s,int num){if(x==n-1&&y==n-1&&num==n*n){if(ans.empty())ans=s;return;}//为最后一次递归设置终止条件，找到答案终止递归（项目结题）for(int i=0;in-1||ny>n-1||nx<0||ny<0)continue;if(val[nx][ny]==true)continue;if(i==1&&(path[nx][ny-1]==3||path[nx+1][ny]==7))continue;if(i==3&&(path[nx-1][ny]==5||path[nx][ny-1]==1))continue;if(i==5&&(path[nx-1][ny]==3||path[nx][ny+1]==7))continue;if(i==7&&(path[nx+1][ny]==1||path[nx][ny+1]==5))continue;if(url>n>>k;for(int i=0;i<n;i++)for(int j=0;j>a[i][j];path[i][j]=-1;}string star;val[0][0]=true;dfs(0,0,0,star,1);if(!ans.empty())cout<<ans<<endl;else cout<<-1<<endl;return 0;}