hdu1016 Prime Ring Problem

dfs，用全局数组和变量保存并更新当前状态。

答案可以直接在搜索结束时打印，n为奇数时方案数为0。

acm.hdu.edu.cn/showproblem.php?pid=1016

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 20;
 7 int n;
 8 int ans[maxn], k;
 9 bool isprime[50];
10 bool vis[20];
11 
12 void init(){
13     memset(isprime, 0, sizeof isprime);
14     isprime[2] = isprime[3] = 1;
15     for(int i = 5; i <= 50; i += 2){
16         bool ok = 1;
17         for(int j = 3; j * j <= i; j += 2){
18             if(i % j == 0){
19                 ok = 0;
20                 break;
21             }
22         }
23         isprime[i] = ok;
24     }
25     memset(vis, 0, sizeof vis);
26 }
27 
28 void dfs(int u){
29     //finished num is u
30     if(u == n && isprime[1 + ans[n - 1]]){
31         printf("%d", ans[0]);
32         for(int i = 1; i < k; i++) printf(" %d", ans[i]);
33         printf("
");
34     }
35     for(int i = 1; i <= n; i++){
36         if(!vis[i] && isprime[i + ans[u - 1]]){
37             vis[i] = 1;
38             ans[k++] = i;
39             dfs(u + 1);
40             vis[i] = 0;
41             --k;
42         }
43     }
44 }
45 
46 void solve(){
47     init();
48     k = 0;
49     ans[k++] = 1;
50     vis[1] = 1;
51     dfs(1);
52 }
53 
54 int main(){
55     int kase = 0;
56     while(~scanf("%d", &n)){
57         printf("Case %d:
", ++kase);
58         solve();
59         printf("
");
60     }
61     return 0;
62 }

View Code