还没有看大佬的代码,分享我的最朴素的思想。。。
遍历一个8*8的图,一行一行进行遍历。
每遍历一个点,就把该点的行,列和左斜线,右斜线都进行标记。
然后继续访问,如果到了最后一行,那么成功。如果还没到最后一行,就已经都标记完了,则进行回溯。
#include<iostream> #include<map> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int maxn=8; int g[maxn][maxn]; vector<int> vec; int res=0,n; void dfs(int now){//now表示当前行 if(now==maxn){ vec.push_back(res); return ; } bool flag=false; for(int i=0;i<maxn;i++){ //第i列 if(g[now][i]==0){ res=res*10+i+1; //用来存储结果 for(int j=i;j<maxn;j++){//把这行后边的列都标记了 if(g[now][j]==0) g[now][j]=now+1; } int l=i-1,r=i+1; for(int j=now+1;j<maxn;j++){//把这列下边的行都标记了 if(g[j][i]==0)g[j][i]=now+1; if(l>=0&&g[j][l]==0) g[j][l]=now+1;//把左斜线的标记了 if(r<maxn&&g[j][r]==0) g[j][r]=now+1;//把右斜线的标记了 l--;r++; } dfs(now+1);//递归进入下一层 for(int j=i;j<maxn;j++){//回溯(把上一轮标记的取消标记) if(g[now][j]==now+1) g[now][j]=0; } l=i-1;r=i+1; for(int j=now+1;j<maxn;j++){//回溯(把上一轮标记的取消标记) if(g[j][i]==now+1) g[j][i]=0; if(l>=0&&g[j][l]==now+1) g[j][l]=0; if(r<maxn&&g[j][r]==now+1) g[j][r]=0; l--;r++; } res-=(i+1); res/=10; } } } int main(){ memset(g,0,sizeof(g)); dfs(0); sort(vec.begin(),vec.end()); while(cin>>n){ cout<<vec[n-1]<<endl; } return 0; }