題見洛谷
位運算版（設(shè)計巧妙，需要回顧，加深理解）
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<vector>#include<queue>using namespace std;int a[20];int ans=0,uplimit,n;void PRint(){ for(int i=1;i<=n;i++) { int x=0;int y=a[i]; while(y) { y=y>>1; x++; } printf("%d ",x); } puts(""); }void dfs(int r,int ld,int rd){ if(r==uplimit){ ans++; if(ans<=3) print(); return; } int pos=uplimit & ~ (r|ld|rd); while(pos!=0) { int p=pos & (-pos);//pos=pos & (~pos+1); pos-=p; a[++a[0]]=p; dfs(r+p,(ld+p)<<1,(rd+p)>>1); a[a[0]]=0;a[0]--;//回溯 }}int main(){ scanf("%d",&n); uplimit=(1<<n)-1; dfs(0,0,0); printf("%d",ans); return 0;}普通版
#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#include<vector>#include<cstring>#include<string>#include<cmath>using namespace std;int n;int ans[100];int tot=0;int fa[100],fl[20],fb[100];void dfs(int k){ if(k>n){ if(tot<3){ for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("/n"); } tot++; } else { for(int i=1;i<=n;i++) if(fl[i]==0&&fa[i+k]==0&&fb[i-k+n]==0) { ans[k]=i; fl[i]=1; fa[i+k]=1; fb[i-k+n]=1; dfs(k+1); fl[i]=0; fa[i+k]=0; fb[i-k+n]=0; } }}int main(){ scanf("%d",&n); dfs(1); printf("%d",tot); return 0;}新聞熱點
疑難解答
