深搜入门题型

骨的诱惑

这道题目还是比较粗暴的呀，不过有很多使用的小技巧适用于走迷宫类的题目。
1、走路的方式可以用两个数组两重循环表示，如最基本的上下左右表示为
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
2、设置flag,到达终点立刻令其等于1，跳出函数
3、由于本题不走回头路，每次经过一个位置，将visit[x][y] 设为1，表示已访问，记得回溯的时候重新将visit改为0；
4、奇偶性剪枝。这里借用大佬的一段话：

1.如果当前时间即步数(step) >= T 而且还没有找到D点，则剪掉。
2.设当前位置(x, y)到D点(dx, dy)的最短距离为s，到达当前位置(x, y)已经花费时间(步数)step，那么，如果题目要求的时间T - step < s，则剪掉。
3. 对于当前位置(x, y)，如果，(T-step-s)是奇数，则剪掉(奇偶剪枝)。
4.如果地图中，可走的点的数目(xnum) < 要求的时间T，则剪掉(路径剪枝)。
————————————————
大佬的csdn名称「chyshnu」
原文链接：https://blog.csdn.net/chyshnu/article/details/6171758/
最后附上我的超长暴力代码：

#include <bits/stdc++.h>
using namespace std;
int l,r,T,n,m,flag;
int vis[200][200];
char a[200][200];
bool gg(int x,int y)
{
	if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==0)
		return true;
	else
		return false;
}
void dfs(int x,int y,int t)
{
	if(t==T-1)
	{
		if(gg(x+1,y)&&a[x+1][y]=='D')flag=1;
		if(gg(x-1,y)&&a[x-1][y]=='D')flag=1;
		if(gg(x,y+1)&&a[x][y+1]=='D')flag=1;
		if(gg(x,y-1)&&a[x][y-1]=='D')flag=1;
		return;
	}
	if(gg(x+1,y)&&a[x+1][y]=='.')
	{
		vis[x+1][y]=1;
		dfs(x+1,y,t+1);
//		if(flag)
//			return;
		vis[x+1][y]=0;
	}
	if(gg(x-1,y)&&a[x-1][y]=='.')
	{
		vis[x-1][y]=1;
		dfs(x-1,y,t+1);
//		if(flag)
//			return;
		vis[x-1][y]=0;
	}
	if(gg(x,y+1)&&a[x][y+1]=='.')
	{
		vis[x][y+1]=1;
		dfs(x,y+1,t+1);
//		if(flag)
//			return;
		vis[x][y+1]=0;
	}
	if(gg(x,y-1)&&a[x][y-1]=='.')
	{
		vis[x][y-1]=1;
		dfs(x,y-1,t+1);
//		if(flag)
//			return;
		vis[x][y-1]=0;
	}
	return;
}
int main()
{
	while(cin>>n>>m>>T)
	{
		memset(vis,0,sizeof(vis));
		int x,y;
		flag=0;
		if(T==0&&n==0&&m==0)
			break;
		for(int i=0;i<n;i++)
			cin>>a[i];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(a[i][j]=='S')
				{
					x=i;y=j;
					vis[i][j]=1;
				}
				if(a[i][j]=='D')
				{
					l=i;r=j;
				}
			}
		}
		dfs(x,y,0);
		if(flag)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;	
	}
}

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;
}