HDU 1016 Prime Ring Problem-蒲公英云

HDU 1016 Prime Ring Problem

原题目链接HDU1016

分类

HDU 素数 DFS

题意

输入一个数n,把1到n的自然数放到一个环里，保证相邻的两个数的和是素数。

样例输入输出

Sample Input

6
8

Sample Output

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

想法

DFS基础题，注意深搜结束条件

代码

249ms

#include<bits/stdc++.h>
using namespace std;
const int maxn =  1111;
int get_prim[maxn]={ 0};
int circle[maxn],vis[maxn],n;
void Get_prim(){ //素数打表 1表示不是素数 
    get_prim[1] = 1; 
    for(int i=2;i<=maxn;i++){ 
        if(!get_prim[i]){ 
            for(int j=i*i;j<=maxn;j+=i){ 
                get_prim[j] = 1;
            }
        }
    }
}
void dfs(int step){ 
    if(step==n+1&&!get_prim[circle[1]+circle[n]]){ //深搜结束条件 
        for(int i=1;i<n;i++)
            printf("%d ",circle[i]);
        printf("%d\n",circle[n]);
    }else{ 
        for(int i=2;i<=n;i++){ 
            if(!vis[i]&&!get_prim[circle[step-1]+i]){ 
                circle[step] = i;//把符合要求的数存入数组 
                vis[i] = 1;//标记 
                dfs(step+1);
                vis[i] = 0;//回溯 
            }
        }
    }
}
int main() { 
    //freopen("in.txt","r",stdin);
    Get_prim();
    int kase=0;
    while(cin >> n&&n){ 
        memset(vis,0,sizeof(vis));
        circle[1] = 1;
        printf("Case %d:\n",++kase);
        dfs(2);
        printf("\n");
    }
    return 0;
}