HDU 1016 Prime Ring Problem

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

 

 

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25493    Accepted Submission(s): 11369

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

 

 

Input

n (0 < n < 20).

 

 

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

 

 

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

 

 

Source

Asia 1996, Shanghai (Mainland China)

 

 

Recommend

JGShining

 

分析：这道题目就是用深度优先遍历的方式来解决的。首先构造素数表，这个我就不多解释了，网上代码和解释多的是。由于环的开始点被定死的，都是1，1先入栈，标记为访问过的数字，用for循环遍历给定范围内的所有数字，遇到与1相加是素数的，停止，就将它放入栈中，标记为访问过的数字，进入DFS函数操作，DFS函数也就是一个迭代过程，用for 循环遍历所有未访问过的 数字，如果与栈顶元素相加为素数，则停止，放入栈中，标记为访问过的数字，一直迭代下去，一直到没有可以用的数字为止（PS：没有可以用的数字就是 情况1：所有数字都被访问过，也就是全部入栈 ；情况2：不是所有数字都被访问过，但是剩下的数字中没有能够和栈顶元素相加和为素数的了）如果此时栈内元素==n,那么说明当前序列符合题目要求，则从栈底到栈顶依次输出所有元素。如果此时栈内元素！=n，说明当前序列不可能是符合题意的子序列，因此必须回溯！！！

回溯是在DFS()后，回溯必须注意要把visit[]中相应的元素还原为未访问（比如说你从1 2 3 4 5 中5不合题意，回溯那么5必须标记为未访问，因为你要得到的序列是 1 2 3 4），并且弹出栈顶元素。

源代码：

//深度优先搜索（DFS）
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

const int MAXN = 50;
const int MAXNA = 21;
bool isPrime[MAXN];
bool isVis[MAXNA];
int arstack[MAXNA];
int total,n;
stack<int> ans;
stack<int> temp;
//初始素数表
void initPrime(){
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i=2;i<MAXN;i++){
        if(isPrime[i]){
            for(int j = 2;j*i<=MAXN;j++)
            isPrime[j*i] = false;
        }
    }
}
void DFS(int x,int count){
    if(count == n && isPrime[x+1]){
        int i=0;
        temp = ans;
        while(!temp.empty()){

            arstack[i++]= temp.top();
            temp.pop();
        }
        for(int j=i-1;j>0;j--){
            printf("%d ",arstack[j]);
        }
        printf("%d\n",arstack[0]);
        return;
    }
    else{

        for(int d=1;d<=n;d++){
            if(!isVis[d] && isPrime[d+x]){
                isVis[d]=1;
                ans.push(d);
                DFS(d,count+1);
                ans.pop();
                isVis[d]=0;

            }
        }
    }
}
main(){
    initPrime();
    int k=1;
    while(scanf("%d",&n)!=EOF){
        while(!ans.empty())ans.pop();
        memset(isVis,0,sizeof(isVis));
        printf("Case %d:\n",k++);
        isVis[1] = 1;
        ans.push(1);
        for(int i=2;i<=n;i++){
            total = 1;
            if(!isVis[i]&&isPrime[1+i]){
                isVis[i] = 1;
                ans.push(i);
                DFS(i,total+1);
                ans.pop();
                isVis[i] = 0;
            }
        }
        printf("\n");
    }

}