搜索杂题：

一、基础的BFS与DFS：

深搜和广搜都可以遍历出在一定限制下可能出现的所有情况，但是朴素的搜索一般复杂度极高，成指数级别，需要用到各种五花八门的优化方式，后面会一一介绍，但基础很重要，几乎不用考虑优化，直接模拟题意就可以了。这篇博文讲的是习题ing。

深搜一般处理有分支的情况，广搜一般解决图上的问题。

（1）深搜：

深度优先搜索算法（英语：Depth-First-Search，简称DFS）。

是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。

P2392 kkksc03考前临时抱佛脚：

显然是深搜，由于左右大脑可以处理同样科目的两个问题，对于每个科目都进行一次深搜，找出每个科目需要的最少时间，那么加起来就是总的最少时间。

那么定义\(dfs(int id,int num)\)，\(id\)为当前科目，\(num\)为目前搜索到这个科目的哪一个任务了。再使用lx，rx表示目前左右大脑所有的时间，每一个任务有两种可能，放在左脑和放在右脑，在深搜玩所有的任务之后，用ans存下最小的时间，最后累加。

P1036 [NOIP2002 普及组] 选数：

建议学一下素数筛，预处理使用素数筛将1e7以内的素数全部筛出来，复杂度\(O(n)\)，这样就可以做到在\(O(1)\)的时间内判断一个数是不是素数。

定义深搜\(dfs(int u,int sum,int pre)\)从前向后搜，分别代表当前已经加了几个数、当前的数值和、应该从第几个数开始选（避免重复），边界条件就是\(u==m\)，这时候判断sum是不是素数，是就\(ans++\)，初始状态显然就是\(dfs(0,0,0)\)。

P2036 [COCI 2008/2009 #2] PERKET：

题意很显然，唯一新颖的就是多了一个必须要加调料的限制和酸度是各个调料乘在一起。深搜写起来要好做一点。

定义深搜\(dfs(int u,int sa,int sb,int flag)\)，分别代表当前是第几个调料、酸度、苦度、用了调料没有。每一个调料都有选与不选两种情况，注意的是当前物品要选就将\(flag\)设为1，没选就继承之前的\(flag\)，边界条件\(u>n\)，如果\(flag\)为1，就与\(ans\)比较，计算出最小值。初始状态也要注意，因为酸度是乘积，所以初始状态应该是\(dfs(1,1,0,0)\)。

关键代码

dfs(u+1,sa,sb,flag);//不选
dfs(u+1,sa*p[u].a,sb+p[u].b,1);//要选

P1101 单词方阵
稍微会麻烦一点的题，由于各个方向都可以，共有八个方向上，左上，左，左下，下，右下，右，右上。而且已经给出了需要找的目标串\(yizhong\)。将整个地图输入，显然，要匹配成功，前两个字符肯定是必须要存在的，于是我们可以遍历图中的\('y'\)字符，在找到\('y'\)字符附近的八个方向是否存在\('i'\)字符，这样我们就可以确定起点与方向。

这时候用深搜，判断以某一点为起点，朝着某一个方向，是否存在目标串，定义深搜状态\(dfs(int sx,int sy,int x,int y,int num)\)，sx，sy代表方向(如\(sx=1，sy=0\)就是右)，x，y代表当前所在的位置，num代表现在是第几个字符了。终止条件\(num==7\)。累加合法的情况。

P2404 自然数的拆分问题：
顶针深搜，非常入门的一道题，从前向后搜就可以了，可以保证是按字典序的大小来的。

定义\(dfs(int he,int c,int qs)\)分别代表当前各数之和，当前有几个数，现在从哪里开始搜(应为要保证各个加数是递增的)，深搜的时候用一个a数组把答案存起来

关键代码：

for(int i=qs;i<=n-1;i++)
{
	a[c]=i;
	dfs(he+i,c+1,i);
	a[c]=0;
}

P1596 [USACO10OCT] Lake Counting S：
采用深搜和广搜都有的一个小trick，染色法。输入map之后，一个个遍历，找到一个字符"W"且这个位置没有被遍历的时候，答案+1，然后从这个点深搜，找出所有与这个点联通的水坑，联通的水坑又深搜的找它联通的水坑，这样向四周扩展，打上标记，然后最后统计答案。

当然这道题广搜也同样可以做，也是可以运用染色的思想。定义\(dfs(x,y)\)就是代表当前的坐标，向八个方向延生，如果有是水坑且还没有打标记的点，就深搜的找。

关键代码：

for(int i=1;i<=8;i++)
{
	int sx=x+fx[i],sy=y+fy[i];（其中fx,fy是方向数组，懒得一个一个方向写）
	if(!vis[sx][sy]&&mapp[sx][sy])//我是预处理了的，如果这里是水坑，mapp[i][j]就为1
	{
		dfs(sx,sy);//深搜
	}
}

P1294 高手去散步：
题面可能有一点绕，需要的前置知识就是邻接矩阵存图（简单地说，如果1点到2点有一条长度为5的边，那么mapp[1][2]=5，通式是mapp[u][v]=w，代表从u到w有一条长度为w的边，邻接矩阵非常占空间，一般处理点数少于2000的图）。

存好图，一次枚举从\(1-n\)每一个点出法最后可以走的最大路程，最后记录这个最大路程输出即可。深搜很简单（如果你明白了邻接矩阵的话）

关键代码：

inline void dfs(int u,int len)//哪个点了，现在走了多远
{
	ans=max(ans,len);//全局变量记录最大的路程
	for(int i=1;i<=n;i++)//邻接矩阵存图，看当前点的所有出边
	{
		if(!vis[i]&&mapp[u][i]>0)//没有到过&有边
		{
			vis[i]=1;//到过了
			dfs(i,mapp[u][i]+len);//去i点，长度加上mapp[u][i]，即u至i的距离
			vis[i]=0;//撤销操作，搜下一个状态
		}
	}
}

CF377A Maze

灰常有意思的一道题，需要运用逆向思维，由于正向模拟似乎有点麻烦，而且要维护剩下的点是联通的，所以不好做。但是如果我们换一个角度，我们在输入的时候统计是点的个数，记作sum，由于它需要我们变k个\('#'\)出来，所以最后会剩下sum-k个点，一开始的点也都是联通的，于是我们利用深搜的性质，从任意一个点出发，向四周扩散，扩散sum-k个点，打上标记，输出的时候，如果当前点打了标记，那么就输出点，否则就输出#。

关键代码：

inline void dfs(int x,int y)
{
	if(sum==res) return ;//到了给定点后就返回
	vis[x][y]=1,sum++;//统计遍历了多少个点
	for(int i=1;i<=4;i++)
	{
		int sx=x+fx[i],sy=y+fy[i];//方向数组
		if(sx<1||sx>n||sy<1||sy>m||mapp[sx][sy]=='#'||vis[sx][sy]) continue;//超出边界和#以及已经走过的点不走
		dfs(sx,sy);
	}
}

P3915 树的分解

前置知识是树的遍历（不会的这道题可以先略过），深搜最大的用处之一就是遍历树，这道题是贪心，深搜的同时记录树的大小，一旦大小等于要求的值，答案就加一，最后判断答案与要求数目是否一样。

关键代码：

inline void dfs(int u,int fa)
{
	siz[u]=1;
	for(int i=head[u];i!=0;i=p[i].next)//使用链式前向星存图
	{
		int v=p[i].to;
		if(v==fa) continue;//树是建的双向边
		dfs(v,u);
		if(siz[v]==k) siz[v]=0,num++;//子树大小满足要求，答案加1，子树贡献归0
		siz[u]+=siz[v];
	}
	if(siz[u]==k) siz[u]=0,num++;//当前节点下的子树满足要求，答案加1，当前节点大小贡献归0
}

P2080 增进感情：
基础深搜题，按照题目所给的要求模拟搜索，每一个事件有做与不做两种可能。

关键代码：

inline void dfs(int u,int sa,int sb)//分别代表目前是第几个事件，小明的好感度，小红的好感度
{
	if(u==n)//搜索边界，最后一个事件
	{
		if(sa+sb>=v)//模拟题意，好感度之和超过v
		{
			ans=1,minn=min(minn,abs(sa-sb));//说明有答案，记录最小差值
		}
		return ;
	}
	dfs(u+1,sa,sb);//不做这个事件
	dfs(u+1,sa+a[u+1],sb+b[u+1]);//做这个事件
}