九度oj 题目1459：Prime ring problem

题目描述：

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.

输入：: n (1 < n < 17).

输出：: 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.

样例输入：

6
8

样例输出：

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

提示：

用printf打印输出。

此题应该用深搜来求解，代码如下

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int n;
 9 
10 int isPrime[42];
11 void getPrime() {
12     memset(isPrime, 0, sizeof(isPrime));
13     for (int i = 2; i <= 40; i++) {
14         if (isPrime[i] == 0) {
15             for (int j = i*2; j <= 40; j += i) {
16                 isPrime[j] = 1;
17             }
18         }
19     }
20 
21 }
22 
23 int flag[20];
24 int ans[20];
25 
26 void dfs(int step) {
27     if (step == n) {
28         int tmp = ans[0] + ans[n - 1];
29         if (isPrime[tmp] == 0) {
30             printf("%d", ans[0]);
31             for (int j = 1; j < n; j++) {
32                 printf(" %d", ans[j]);
33             }
34             puts("");
35         }
36         return;
37     }
38     for (int i = 2; i <= n; i++) {
39         if (flag[i] == 0) {
40             if (step == 0) {
41                 flag[i] = 1;
42                 ans[step] = i;
43                 dfs(step + 1);
44                 flag[i] = 0;
45             }
46             else {
47                 int tmp = ans[step - 1] + i;
48                 if (isPrime[tmp] == 0) {
49                     flag[i] = 1;
50                     ans[step] = i;
51                     dfs(step + 1);
52                     flag[i] = 0;
53                 }
54             }
55         }
56     }
57 }
58 int main(int argc, char const *argv[])
59 {
60     getPrime();
61     memset(flag, 0, sizeof(flag));
62     int p = 1;
63     while (scanf("%d", &n) != EOF) {
64         printf("Case %d:
", p);
65         flag[1] = 1;
66         ans[0] = 1;
67         dfs(1);
68         p++;
69         puts("");
70     }
71 
72     return 0;
73 }