深搜搜搜搜搜

题目一、hdu1016素数环

第一个独立完成的深搜啊，直接上代码。

#include <bits/stdc++.h>
using namespace std;
int n,a[30],vis[30],b[30],flag=0;
bool sushu(int a,int b)//判断是否满足和为素数
{
	int c=a+b,i;
	for(i=2;i<c;i++)
	{
		if(c%i==0)
			break;
	}
	if(i==c)
		return true;
	else
		return false;
}
void dfs(int num)
{
	if(num==n+1)
	{
		flag=1;//这里是关键。成功了，flag应为1，提示b数组应该回溯了
		for(int i=1;i<=num-1;i++)//打印结果
		{
			cout<<b[i];
			if(i!=num-1)
				cout<<" ";
		}
		cout<<endl;
//		b[num]=0;
		return;
	}
		for(int i=2;i<=n;i++)//b[i]一定为1的，所以从i=2开始
		{
			if(vis[i]==0&&sushu(a[i],b[num-1]))
			{
				if(num==n&&!sushu(a[i],b[1]))//由于圆环，最后一次判断两头
					break;
				vis[i]=1;
				b[num]=a[i];
				dfs(num+1);
				if(flag)
				{
				/*	memset(b,0,sizeof(b));
					b[1]=1;
					flag=0;*/
					b[num]=0;//成功了当然得刷掉上一步啊！
					flag=0;
				}
				vis[i]=0;//回溯
			}
		}
}
int main()
{
	int z=0;
	while(cin>>n)
	{
		flag=0;
		z++;
		cout<<"Case "<<z<<":"<<endl;
		memset(vis,0,sizeof(vis));
		memset(b,0,sizeof(b));
		b[1]=1;
		for(int i=1;i<=n;i++)
			a[i]=i;
		dfs(2);
		cout<<endl;
	}
}

题目二：hdu1015

直接上代码。

在这里插入代码片
#include <bits/stdc++.h>
using namespace std;
char a[20],ans[6],vis[20],sk[6];//sk数组保存结果
int l,zhi,flag=0;//flag为判断找没找到
int cmp(char a,char b)
{
	return a>b;//重要的一步，排序保证第一个搜到的是结果
}
void dfs(int num,int sumn)//num表示第几个字符，sumn为当前总和
{
	if(num==6&&sumn!=zhi)
		return;
	if(num==6&&sumn==zhi)
	{
		flag=1;//标记找到
		return;
	}
	for(int i=0;i<l;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;//标记是否用过当前字符
			sk[num-1]=a[i];
			dfs(num+1,sumn-pow(-1,num)*pow(a[i]-'A'+1,num));
			if(flag)///超级重要的一步。找到了直接返回呀！
				return;
			sk[num-1]=0;//开始蠢了。没想到回溯应该抹去SK数组
			vis[i]=0;
		}
	}
}
int main()
{
	while(cin>>zhi)
	{
		if(zhi==0)
			break;
		flag=0;
		memset(vis,0,sizeof(vis));
		cin>>a;
		l=strlen(a);
		sort(a,a+l,cmp);
		dfs(1,0);
		if(flag)
			cout<<sk<<endl;
		else
			cout<<"no solution"<<endl;
	}
	return 0;
}