HUD 1016 Prime Ring Problem（简单DFS）

 

 

const int N=20+5; const int prime[]= {0,0,1,1,0, 1,0,1,0,0,0, 1,0,1,0,0,0, 1,0,1,0,0,0, 1,0,0,0,0,0, 1,0,1,0,0,0, 0,0,1,0,0,0 };//前40个素数打表 int n,m,t; int i,j,k; int a[N]; bool vis[N]; bool flag; void DFS(int step) { //debug(step); //debug(n); if(step==n){ if(prime[ a[step]+a[1] ]){ for(int i=1;i<=step;i++) printf("%d%c",a[i],i==step? '\n' :' '); } } else for(int i=2;i<=n;i++){ if(!vis[i] && prime[ a[step]+i ]){ vis[i]=1; a[step+1]=i; DFS(step+1); vis[i]=0; } } } int main() { //IOS; int num=0; while(~sd(n)){ ms(vis,0); a[1]=1; printf("Case %d:\n",++num); DFS(1); puts(""); } //PAUSE; return 0; }