HDU1016数字排列搜索

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20363 Accepted Submission(s): 9115

Problem Description

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.

Input

n (0 < n < 20).

Output

The 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:
4 3 2 5 6
6 5 2 3 4

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

Source

Asia 1996, Shanghai (Mainland China)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <cassert>
11 #include <set>
12 #include <sstream>
13 #include <map>
14 using namespace std ;
15 #ifdef DeBUG
16 #define bug assert
17 #else
18 #define bug //
19 #endif
20 #define zero {0}
21 #define INF 2000000000
22 #define eps 1e-6
23 int cnt=1;
24 int a[30];//记录序列 
25 int used[30];//记录i是否使用 
26 int prime[]={
27 0,1,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,
28 1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,
29 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0
30 };
31 int n;
32 void print()//打印数组 
33 {
34     for(int i=1;i<n;i++)
35     printf("%d ",a[i]);
36     printf("%d
",a[n]);
37 }
38 void dfs(int depth)
39 {
40     if(depth==n+1)
41     {
42         if(prime[a[n]+1])//判断最后一个元素与第一个元素是否为素数 
43         {
44             print();
45         }
46         return;
47     }
48     else
49     {
50         for(int i=1;i<=n;i++)
51         {
52             if(!used[i]&&prime[a[depth-1]+i])
53             {
54                 a[depth]=i;
55                 used[i]=true;
56             //    print();
57                 dfs(depth+1);
58                 used[i]=false;
59                 a[depth]=0;
60             }
61         }
62     }
63 }
64 int main()
65 {
66 
67 
68     #ifdef DeBUGs 
69         freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
70 //    freopen("C:\Users\Sky\Desktop\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
71     #endif
72     while(scanf("%d",&n)+1)
73     {
74         memset(a,0,sizeof(a));
75         memset(used,0,sizeof(used));
76         printf("Case %d:
",cnt++);
77         a[1]=1;
78         used[1]=1;
79         dfs(2);
80         printf("
");
81     }
82     return 0;
83 }

View Code