写在前面

人有的时候总是得面对选择

断断续续接触ACM也有差不多两年的时间了，但是还没有系统学习过什么算法，趁着现在还有些时间，把基础的算法弄清楚吧。先从使用较为广泛的搜索算法开始吧！

DFS（深度优先搜索）

这里讲的dfs是最最最最最基础的dfs，不接触剪枝和回溯。所谓dfs，就是沿着一个点一直搜索其所有的可能性，搜到头之后再回溯到上一个状态继续搜索别的可能性。
本来想画个图说的清楚一点的，但是估计也没人看，所以就省略了，是一个二叉树遍历的图。
这里最重要的就是回溯也就是return的条件，这是整个dfs递归程序的出口，所以这一点一定要仔细考虑，不要漏掉某一种情况导致程序递归次数过多。

经典例题

题目一传送门https://www.luogu.com.cn/problem/P2036
题目二传送门https://www.luogu.com.cn/problem/P1605
题目三传送门https://www.luogu.com.cn/problem/P1596

题目一

本题的一个小小注意点是酸度的初始值应该为1而不是0，如果是0的话，后面所有的酸度与其相乘之后的结果都会是0。

这里搜索的思路是每一种配料都有一个酸度和苦度，我们分别把选这个配料和不选这个配料的所有情况都列出来，从中选取酸度苦度绝对值之差最小的结果即可。这里我们注意一下返回条件，题目说了至少要选取一种配料，而最多只有n种配料（0~n-1）。因此，我们看看当查询到所有配料的时候，如果恰好是所有配料都不选，也就是初始值没有任何变化的时候，进行返回操作。当然，我们也要记录一个最优结果的值，进行返回。

#include<bits/stdc++.h>
#define ll long long
/*
#include <iomanip>
cout<<setiosflags(ios::fixed)<<setprecision(n);//保留n位小数输出 
*/ 
using namespace std;
int ans=0x7fffffff;
int n;
struct node
{
	int s;
	int b;
}a[20];
void dfs(int i,int s,int b)//s表示酸度，b表示苦度 
{
	if(i>n-1)
	{
		if(s==1&&b==0)
		return;
		ans=min(abs(s-b),ans);
		return;
	}
	dfs(i+1,s*a[i].s,b+a[i].b);
	dfs(i+1,s,b);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].s>>a[i].b;
	}
	dfs(0,1,0);
	cout<<ans<<endl;
    return 0;
}

题目二

迷宫问题是一道很经典的DFS问题，本题的要求是统计起点到终点的路径条数。这就很简单了，从起点开始搜索所有的情况，只要能到达终点，就将结果数+1，直到搜索完所有的情况。这里需要注意的问题主要有以下几点：
1、注意不同方向的走法，这里是四方向的，后面题目三会介绍八方向的。
2、in函数是判断当前的位置是否合法，是不是超出了地图边界？
3、在后面的if判断中，我们要进行的是如下几个问题的判断：这个点是不是之前已经走过了？这个地方是不是有障碍物？只有这个点合法，我们才能进行搜索操作，否则直接找下一个点。

#include<bits/stdc++.h>
#define ll long long
/*
#include <iomanip>
cout<<setiosflags(ios::fixed)<<setprecision(n);//保留n位小数输出 
*/ 
using namespace std;
int m,n,sx,sy,tx,ty,t;
int sum=0;
int Map[10][10];
int vis[10][10];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool in(int x,int y)
{
	if(x<=n&&x>=1&&y<=m&&y>=1)
	{
		return true;	
	}
	else
	return false;	
} 
int dfs(int x,int y)
{
	//如果最终能到达终点，要给路径总条数+1
	if(x==tx&&y==ty)
	{
		sum++;
	}
	vis[x][y]=1;//标记这个点已经被访问了
	for(int i=1;i<=4;i++)
	{
		//nx，ny表示当前的位置
		int nx=x+dir[i-1][0];
		int ny=y+dir[i-1][1];
		//判断当前位置是否合法
		if(in(nx,ny)==true&&vis[nx][ny]!=1&&Map[nx][ny]!=1) 
		dfs(nx,ny);
	}
	vis[x][y]=0;//将这个点恢复到原来的情况，不影响从这个点搜索其他点
	return sum;
}
int main()
{
	int xx=0,yy=0;
	cin>>n>>m>>t;
	cin>>sx>>sy>>tx>>ty;
	for(int i=0;i<t;i++)
	{
		scanf("%d %d",&xx,&yy);
		Map[xx][yy]=1;
	}
	cout<<dfs(sx,sy)<<endl;
    return 0;
}

题目三

题目三和题目二的区别就是题目三有八个方向，而且题目三在检查完状态后**不用将这个点恢复到原来的状态！！因为从这个点开始搜，一下子就把这一摊水坑都给搜完了。**所以本题所问的水坑的数量，其实就是搜索的次数！

#include<bits/stdc++.h>
#define ll long long
/*
#include <iomanip>
cout<<setiosflags(ios::fixed)<<setprecision(n);//保留n位小数输出 
*/ 
using namespace std;
char g[105][105];
int n,m;
int ans;
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
void dfs(int x,int y)
{
	g[x][y]='.';//将这个点标记为以访问
	for(int i=0;i<8;i++)
	{
		if(x>=0&&x<n&&y>=0&&y<m&&g[x+dir[i][0]][y+dir[i][1]]=='W')
		{
			dfs(x+dir[i][0],y+dir[i][1]);
		}
	}
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		scanf("%s",&g[i]);
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(g[i][j]=='W')
			{
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans<<endl;
    return 0;
}