HDU1016 Prime Ring Problem DFS 简单题

题意：输入n，代表有一个n个节点的环，然后在节点分别填入1到n这n个数，规定，第一个填入的必须是1.

0<n<40

要求填入后满足，任意相邻的2个节点的数之和为素数。

将满足条件的填法按照字典序的顺序小到大依次输出。

其实刚开始做的时候我觉得这道题会做很久的，想好后就开始打了，打着打着发现这道题打好了，有点意外，原来这么简单。

注意回溯，在每次DFS后要记得把状态恢复原样，比如这道题是每次DFS后都要把当前DFS的数字i恢复为vis[i]=false;

先考虑好初始化，结束条件，回溯。

先来一个prime[40],把40里面的素数先为true.

dfs（int cnt ,int dep)

cnt 当前要填入的数

dep 填到了第几个数了

vis[i] i这个数填了没有

ans 存储已经填入的数，填入的数有n个且符合条件就可以开始输入了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 bool prime[43];
 7 bool vis[25];
 8 int tot,n;
 9 int ans[25];
10 void dfs(int cnt,int dep)
11 {
12     ans[dep]=cnt;
13     vis[cnt]=true;
14     if(dep==n&&prime[cnt+1])
15     {
16         for(int i=1;i<n;i++)
17             printf("%d ",ans[i]);
18         printf("%d
",ans[n]);
19     }
20     for(int i=2;i<=n;i++)
21     {
22         if(!vis[i]&&prime[i+cnt])
23         {
24             dfs(i,dep+1);
25             vis[i]=false;
26         }
27     }
28 }
29 int main()
30 {
31     memset(prime,true,sizeof(prime));
32     prime[0]=prime[1]=true;
33     for(int i=2;i<=40;i++)
34     {
35         int m=sqrt(i);
36         for(int j=2;j<=m;j++)
37         {
38             if(i%j==0)
39             {
40                 prime[i]=false;
41                 break;
42             }
43         }
44     }
45     int cas=0;
46     while(scanf("%d",&n)!=EOF)
47     {
48         cas++;
49         printf("Case %d:
",cas);
50         memset(vis,false,sizeof(vis));
51         memset(ans,0,sizeof(ans));
52         tot=0;
53         dfs(1,1);
54         printf("
");
55     }
56     return 0;
57 }

View Code