hdu1016Prime Ring Problem

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

这几天做题第一次一次性AC 自信心上涨

简单dfs

一个大圈中有n个小圈填进去数相邻圈中数的和为素数

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int x[21][21],v,f,y[21],c[21],n;
 4 int prime(int x)
 5 {
 6     int i,flag = 1;
 7     for(i = 2; i < x ; i++)
 8         if(x%i == 0)
 9         {
10             flag = 0;
11             break;
12         }
13     return flag;
14 }
15 void dfs(int i, int v)
16 {
17     int j;
18     y[v] = i;
19     if(v==n-1)
20     {
21         for(i = 0; i < n ; i++)
22         {
23             if(i!=0)
24             printf(" ");
25             printf("%d", y[i]);
26         }
27         printf("\n");
28     }
29     else
30     {
31         for(j = 2 ; j <= n ; j++)
32             if(prime(i+j)&&c[j] == 0)
33             {
34                 if(v == n-2)
35                 if(!prime(1+j))
36                 return;
37                 c[j] = 1;
38                 dfs(j,v+1);
39                 c[j] = 0;
40             }
41     }
42 }
43 int main()
44 {
45     int i, j,k = 0;
46     while(scanf("%d", &n)!=EOF)
47     {
48         memset(x,0,sizeof(x));
49         memset(c,0,sizeof(c));
50         k++;
51         y[0] = 1;
52         c[1] = 1;
53         printf("Case %d:\n",k);
54         dfs(1,0);
55         puts("");
56     }
57     return 0;
58 }