HDOJ 1016 Prime Ring Problem

题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1016


分析:这是素数环的问题,素数环是标准的DFS问题。
直接用next_permutaion()测试会超时。
这里使用回溯法。
这里有一篇在网上看到的对DFS的理解的文章,和大家分享下:
http://www.cppleyuan.com/redirect.php?tid=2683&goto=lastpost#lastpost
解答报告:
根据本题总结dfs的主要步骤和方法:
1. 找搜索出口条件,即搜索到最深层时的操作
2. Dfs采用递归搜索,在遍历后返回时标记已经遍历的节点
3. 注意入口条件的满足
4. 画出递归搜索图查看函数是否满足要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
 
int p[40], vis[20],result[20];
int n;
 
void DFS(int begin, int num)    // begin表示前一个字母,num表示后一个字母
{
    int i, j;
    if(num == n && p[result[1]+result[num]])   //递归边界。注意测试第一个数和最后一个数
    {
        for(i=1; i<=n; ++i)    //打印方案
            printf(i==1?"%d":" %d", result[i]);
        printf("\n");
        return;
    }
    for(i=2; i<=n; ++i)       //尝试放置每一个数i
        if(p[begin+i] && vis[i] == 0)
        {
            result[num+1] = i;
            vis[i] = 1;
            DFS(i, num+1);
            vis[i] = 0;
        }
}
 
int main()
{
    p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17]
    = p[19] = p[23] = p[29] = p[31] = p[37] = 1;
    int i, nCases = 1;
    while(scanf("%d", &n) != EOF)
    {
        printf("Case %d:\n", nCases++);
        result[1] = 1;
        if(n%2 == 0)
            DFS(1, 1);
        printf("\n");
        memset(vis, 0, sizeof(vis));
    }
    return 0;
 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1016 Prime Ring Problem》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注