P1219 N皇后（位运算&普通dfs）

2019-11-11 03:28:15

字体：大中小

来源：转载

供稿：网友

题见洛谷

位运算版（设计巧妙，需要回顾，加深理解）

#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;}

上一篇：生理周期

下一篇：蓝桥杯 2016 省赛 A 方格填数