题目链接:
构造法很牛逼啊，把这个搜索的题直接变成了打表。
我用dfs写了一下。
构造法公式（序列）：
一、当n mod 6 != 2 或 n mod 6 != 3时：[2,4,6,8,...,n],[1,3,5,7,...,n-1] (n为偶数)
[2,4,6,8,...,n-1],[1,3,5,7,...,n ] (n为奇数)
二、当n mod 6 == 2 或 n mod 6 == 3时(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)
[k,k+2,k+4,...,n],[2,4,...,k-2],[k+3,k+5,...,n-1],[1,3,5,...,k+1] (k为偶数,n为偶数)
[k,k+2,k+4,...,n-1],[2,4,...,k-2],[k+3,k+5,...,n-2],[1,3,5,...,k+1],[n] (k为偶数,n为奇数)[k,k+2,k+4,...,n-1],[1,3,5,...,k-2],[k+3,...,n],[2,4,...,k+1] (k为奇数,n为偶数)[k,k+2,k+4,...,n-2],[1,3,5,...,k-2],[k+3,...,n-1],[2,4,...,k+1],[n ] (k为奇数,n为奇数)
这个规律我是没有搞懂的，反正很牛就是了。
我也用dfs写了一下，虽然我知道肯定会T，DFS30层就爆栈了，更何况这里是300层，就当是熟悉一下DFS了。
两种方法贴上。
#include#include int n;int ans = 0;int maps[305][305] = { 0};bool judge(int k,int i){ for(int j=1; j<=n&&j!=i; j++) if(maps[k][j]==1) return false; for(int j=1; j<=n&&j!=k; j++) if(maps[j][i]==1) return false; for(int j=1; k+j<=n&&i+j<=n; j++) { if(maps[k+j][i+j]==1) return false; } for(int j=1; k-j>=1&&i-j>=1; j++) { if(maps[k-j][i-j]==1) return false; } for(int j=1; k-j>=1&&i+j<=n; j++) { if(maps[k-j][i+j]==1) return false; } for(int j=1; k+j<=n&&i-j>=1; j++) { if(maps[k+j][i-j]==1) return false; } return true;}bool dfs(int k){ if(k>n) { ans ++; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(maps[i][j]) printf("%d",j); } } printf("\n"); return true; } for(int i=1; i<=n; i++) { if(judge(k,i)) { maps[k][i] = 1; if(dfs(k+1)) return true; maps[k][i] = 0; } } return false;}int main(){ while(scanf("%d",&n),n) { memset(maps,0,sizeof(maps)); for(int i=1; i<=n; i++) { maps[1][i] = 1; if(dfs(2)) break; maps[1][i] = 0; } //printf("%d\n",ans); } return 0;}
#includeint main(){ int n; while(scanf("%d",&n),n) { if(n%6!=2&&n%6!=3) { if(n%2==0) { for(int i=2;i<=n;i+=2) printf("%d ",i); for(int i=1;i<=n-3;i+=2) printf("%d ",i); printf("%d\n",n-1); } else { for(int i=2;i<=n-1;i+=2) printf("%d ",i); for(int i=1;i<=n-2;i+=2) printf("%d ",i); printf("%d\n",n); } } else { if(n%2==0) { int k=n/2; if(k%2==0) { for(int i=k;i<=n;i+=2) printf("%d ",i); for(int i=2;i<=k-2;i+=2) printf("%d ",i); for(int i=k+3;i<=n-1;i+=2) printf("%d ",i); for(int i=1;i<=k-1;i+=2) printf("%d ",i); printf("%d\n",k+1); } else { for(int i=k;i<=n-1;i+=2) printf("%d ",i); for(int i=1;i<=k-2;i+=2) printf("%d ",i); for(int i=k+3;i<=n;i+=2) printf("%d ",i); for(int i=2;i<=k-1;i+=2) printf("%d ",i); printf("%d\n",k+1); } } else { int k=(n-1)/2; if(k%2==0) { for(int i=k;i<=n-1;i+=2) printf("%d ",i); for(int i=2;i<=k-2;i+=2) printf("%d ",i); for(int i=k+3;i<=n-2;i+=2) printf("%d ",i); for(int i=1;i<=k+1;i+=2) printf("%d ",i); printf("%d\n",n); } else { for(int i=k;i<=n-2;i+=2) printf("%d ",i); for(int i=1;i<=k-2;i+=2) printf("%d ",i); for(int i=k+3;i<=n-1;i+=2) printf("%d ",i); for(int i=2;i<=k+1;i+=2) printf("%d ",i); printf("%d\n",n); } } } } return 0;}