Prime Ring Problem hdu-1016 DFS

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Inputn (0 < n < 20).
OutputThe output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

给你一个数n  1-n组成一个环 相邻的两个数之和要是素数（所以同时要保证头和尾的和是素数）
DFS 基础题 
核心代码就一丢丢  很容易看懂

 1 #include <iostream>
 2 using namespace std;
 3 #include<string.h>
 4 #include<set>
 5 #include<stdio.h>
 6 #include<math.h>
 7 #include<queue>
 8 #include<map>
 9 #include<algorithm>
10 #include<cstdio>
11 #include<cmath>
12 #include<cstring>
13 #include <cstdio>
14 #include <cstdlib>
15 #include<stack>
16 int n;
17 int a[25];
18 int b[25];
19 int sushu(int x)
20 {
21     int s=(int)sqrt(x);
22     for(int i=2;i<=s;i++)
23     {
24         if(x%i==0)
25             return 0;
26     }
27     return 1;
28 }
29 void dfs(int x)
30 {
31     if(x==n&&sushu(a[1]+a[n]))
32     {
33         int flag=0;
34         for(int i=1;i<=n;i++)
35         {
36             if(!flag)
37             {
38                 flag=1;
39                 printf("%d",a[i]);
40             }
41             else
42             {
43                 printf(" %d",a[i]);
44             }
45         }
46         printf("
");
47         return;
48     }
49     for(int i=2;i<=n;i++)
50     {
51         if(b[i]==0&&sushu(a[x]+i))
52         {
53             //cout<<i<<endl;
54             b[i]=1;
55             a[x+1]=i;
56             dfs(x+1);
57             b[i]=0;
58         }
59     }
60 }
61 int main()
62 {
63     int add=0;
64     while(~scanf("%d",&n))
65     {
66         memset(a,0,sizeof(a));
67         memset(b,0,sizeof(b));
68         a[1]=1;
69         printf("Case %d:
",++add);
70         dfs(1);
71         printf("
");
72     }
73     return 0;
74 }

View Code

讲道理输入是奇数的时候直接跳过dfs就好所以我加了个判断，结果时间还变长了一点，编程就像女人，永远搞不懂她。

贴上加判断的AC