学步园

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.

n (0 < n < 20).

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.

6
8

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
#include<iostream>
#include<cstring>
using namespace std;

int map[22][22],vist[22],n;
int stack[22],top;

int prim(int n)//判断是不是素数
{
    int i;
    for(i=2;i*i<=n;i++)
    if(n%i==0)
    return 0;
    return 1;
}

void print_stack()//输出栈中的元素
{
    int i;
    cout<<stack[1];
    for(i=2;i<=top;i++)
    cout<<' '<<stack[i];
    cout<<endl;
}

void DFS(int x)
{
    int i;

   stack[++top]=x;
   vist[x]=1;
    for(i=1;i<=n;i++)
    if(map[x][i]&&vist[i]==0)
    {
        DFS(i);
    }
    if(top==n&&prim(stack[top]+stack[1]))
    {
        print_stack();
    }

     vist[x]=0;  top--;
}

int main()
{
    memset(map,0,sizeof(map));
    int i,j,k=0;

    for(i=1;i<=20;i++)//建立一个素数图表，是素数为1，否则为0
    for(j=1;j<=20;j++)
    if(prim(i+j))
    map[i][j]=1;

    map[1][1]=0;

    while(cin>>n)
    {

        memset(vist,0,sizeof(vist));//每次输入都要清0
        top=0; k++;         //top表示栈顶
         cout<<"Case "<<k<<':'<<endl;
        DFS(1);      //每次都是以 1 为起始点
        cout<<endl;
    }
}