HDU1016-Prime Ring Problem

Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26682    Accepted Submission(s): 11908

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)
 

题意：找出N的各个排列（只要1开头的），相邻两个数的和必须是素数（包括尾部和头部）

用来练习广搜的水题，其实这一题用DFS非常好解决，但是为了练广搜，我把好好的
一个水题做成了难题......
超级大水题，时间竟然过了
AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
   int num[25];
   int k;
   int vis[25];
   node(){
      k=0;
      memset(num,0,sizeof(num));
      memset(vis,0,sizeof(vis));
   }
};
int vis[25],a[25],prime[110],cnt=1;
int IsPrime(int n)
{
    int i;
    if(n==1||n==2)
    return 1;
    for(i=2;i*i<=n;i++)
    if(n%i==0) return 0;
    return 1;
}
void BFS(int n)
{
   queue<node> q;
   node a,b;
   int i,j,k;
   a.num[0]=1;
   a.k++;
   a.vis[1]=1;
   q.push(a);
   while(!q.empty())
   {
      b=q.front();
      q.pop();
      if(b.k==n)
      {
         if(prime[b.num[0]+b.num[n-1]]==0)
         {
            continue;
         }
         else
         {
            printf("%d",b.num[0]);//PE了一次
            for(j=1;j<n;j++)
            printf(" %d",b.num[j]);
            puts("");
         }
      }
      for(i=1;i<=n;i++)
      {
         if(prime[(b.num[b.k-1]+i)]&&b.vis[i]!=1)
         {
            b.num[b.k++]=i;
            b.vis[i]=1;
            q.push(b);
            b.k--;
            b.vis[i]=0;
         }
      }
   }

   
}
int main()
{
   int i,j,n,m;
   memset(prime,0,sizeof(prime));
   for(i=1;i<=100;i++)//素数打表
   {
     if(IsPrime(i))
     prime[i]=1;
   }
   while(scanf("%d",&n)!=EOF)
   {
      memset(vis,0,sizeof(vis));
      printf("Case %d:\n",cnt++);
      BFS(n);
      puts("");
   }
   return 0;   
}
//PS:真他娘折腾人...