HDU 1016 Prime Ring Problem（深搜）

题目链接：HDU 1016 Prime Ring Problem

有n个位置，有n个数，第一个位置放1，求剩下位置满足条件（相邻和为素数）的一个全排列。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
const int maxn = 25; 
using namespace std;
int a[maxn];	//记录每个位置上的数字 
int vis[maxn];
int n;

int pd(int x, int y)	//判断两个数的和是否为素数 
{
	int tmp = x+y;
	if(tmp<2)
		return 0;
	
	for(int i=2;i*i<=tmp;i++)
		if(tmp%i==0)
			return 0;
	return 1;	
}

void print()	//打印 
{
	printf("%d",a[1]);
	for(int i=2;i<=n;i++)
		printf(" %d",a[i]);
	printf("\n");
}

void search(int t)	//第一个位置固定放1, 所以从第二个位置开始，遍历2~n位置 
{
	for(int i=2;i<=n;i++)	//有 2~n个数可选 
	{
		if(pd(a[t-1],i)&&vis[i]==0)		//判断与前一个数是否构成素数及该数是否可用 
		{
			a[t] = i;
			vis[i] = 1;	//标记为已使用
			
			if(t==n)
			{
				if(pd(a[n],a[1]))
					print();
			}
			else
			{
				search(t+1);	//寻找下一个位置 
			}
			
			vis[i] = 0; 
		}	
	}
}




int main()
{
	int cnt = 0;
	while(cin>>n)
	{
		memset(vis,0,sizeof(vis));
		a[1] = 1;
		printf("Case %d:\n",++cnt);
		search(2);	//从第二个位置开始 
		printf("\n");	//每个样例之间有个空行
	}
}