HDU1016 Prime Ring Problem 简单dfs

数据比较小，可以先枚举出范围内所有的素数用来作判断。注意递归条件。

 1 #include<stdio.h>
 2 int n;
 3 int a[20],v[20];
 4 int prime[12]={2,3,5,7,11,13,17,19,23,29,31,37};
 5 int check(int a)
 6 {
 7     for(int i=0;i<12;i++)
 8         if(a==prime[i]) return 1;
 9     return 0;
10 }
11 int dfs(int count,int start)
12 {
13     if(count==n&&check(a[n-1]+1))
14     {
15         printf("1");
16         for(int i=1;i<n;i++)
17             printf(" %d",a[i]);
18         printf("
");    
19     }
20     for(int i=2;i<=n;i++)
21         if(!v[i]&&check(start+i))  
22         {
23             v[i]=1;
24             a[count]=i;
25             dfs(count+1,i);
26             v[i]=0;    
27         }  
28 }
29 int main()
30 {
31     int k=1;
32     while(scanf("%d",&n)!=EOF)
33     {
34         for(int i=0;i<=n;i++)
35             v[i]=0;
36         printf("Case %d:
",k++);
37         dfs(1,1);
38         printf("
");
39     }    
40 }