HDU 1016 Prime Ring Problem DFS

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 int n,k;
 7 int num[13]={0,2,3,5,7,11,13,17,19,23,29,33,37};
 8 int check[21];
 9 bool use[21];
10 int before;
11 bool panduan(int a)
12 {
13     for (int i=1;i<=12;++i)
14     {
15         if (a==num[i])
16         return true;
17     }
18     return false;
19 }
20 void search(int x,int nn)
21 { 
22 int t;
23     if (nn==n)
24     {   
25         
26         if (panduan(x+1)==true)
27         {
28         
29         for(int i=1;i<n;++i)
30         printf("%d ",check[i]);
31         printf("%d\n",check[n]);
32         }
33         return;
34     }
35     for (int i=2;i<=n;++i)
36     {
37         if (use[i]==false&&panduan(i+before)==true)
38         {
39             check[nn+1]=i;
40             use[i]=true;
41             t=before;
42             before=i;
43             search(i,nn+1);
44             check[nn+1]=0;
45             use[i]=false;
46             before=t;
47         }
48     }
49 }
50 int main(){
51     k=0;
52     while(scanf("%d",&n)!=EOF)
53     {
54 
55         for(int i=1;i<=n;++i)
56         {
57         check[i]=0;
58         use[i]=false;
59         }
60         use[1]=true;
61         check[1]=1;
62         int xx=1;
63         k++;
64         
65         printf("Case %d:\n",k);
66         if(xx!=n)
67        {
68         before=1;
69         search(1,1);
70         }else printf("1");
71         printf("\n");
72     }
73     return 0;
74 }