搜索是一个很好用的东西下面来介绍一下搜索
深度优先搜索(dfs)
深度优先搜索总结起来就是不撞南墙不会头，他的复杂度是O( 2^n ) ，这个复杂度很高后面会讲到剪枝可以优化复杂度
深度优先搜索的具体步骤是:
1. 判断到达边界，记录答案 return
2. 枚举各个方案
下面给出伪代码
void dfs(int x)
{
if(/*到达边界*/)
{
//记录答案
return;
}
//决策一
dfs(x+1);
//决策二
dfs(x+1);
}
广度优先搜索(bfs)
广搜就是从起点开始搜索，保证每种状态只会到达一次
广搜常用在最短路（边权为 1 ）算法，因为每种状态最多经过一次，所以最先到终点就是最有的。
广度优先搜索的具体步骤是：
1. 处理起点
2. 获取队首信息
3. 处理各种方案
下面给出迷宫类最短路的伪代码
void bfs(int x,int y)
{
queue<node>q;
vis[x][y]=1;
q.push({x,y,ans});
//处理起始点
while(!q.empty())
{
node now=q.front();//获取新的点
q.pop();
if(/*到达边界*/)
{
cout<<now.ans;
return;
}
for(int i=0;i<4;++i)
{
//获取下一步的位置
if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='#')//满足条件
{
a[nx][ny]='1';//标记，很重要不然会多次搜索
q.push({nx,ny,now.ans+1});//压入队列（继续搜索）
}
}
}
}
剪枝
剪枝用于 dfs ，可以优化我们的时间复杂度，一般分为一下几种
1. 最优性剪枝，比如你要求最短路但是你目前的 ans ≥ 目前找到的最小值直接 return;。
2. 可行性剪枝，如果你发现一些状态不可能到达终点（边界）直接 return;。
3. 顺序性剪枝，例如背包问题（用 dfs 写）我没可以让数组按重量排序，这样可以尽可能的减少搜索次数。
下面对于每个剪枝做个伪代码
1. 最优性剪枝
void dfs(int x,int s)//s是目前代价
{
//ans是目前的最小答案
if(s>=ans) return;
//do something
}
2. 可行性剪枝
例如你的目标是装满背包
void dfs(int x,int s)//s是目前代价
{
//p为后缀重量和,v是目标重量
if(s+p[x]<v) return;
//do something
}
3. 顺序性剪枝
bool cmp(int x,int y)
{
return x>y;
}
void dfs(int x)
{
//do something
}
int main()
{
// do some thing
sort(a+1,a+1+n,cmp);
}
折半搜索
折半搜索就是把要搜索的东西分成两半进行搜索，然后统计答案。
复杂度O( 2^n \times 2)
具体步骤是：
1. 搜索前面一半记录答案
2. 搜索后面一半统计答案
上例题
https://www.luogu.com.cn/problem/CF1006F
我们发现直接搜索是要超时的，这时我们可以用折半搜索。
直接上代码讲解
void dfs1(int x,int y,long long v)
{
if(x+y==(n+m)/2+1)//折半
{
p[x][y][v^a[x][y]]++;//记录这个状态的答案数
return;
}
for(int i=0;i<2;++i)//普通的搜索
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<=n&&ny<=m) dfs1(nx,ny,v^a[nx][ny]);
}
}
void dfs2(int x,int y,long long v)
{
if(x+y==(n+m)/2+1)//折半
{
s+=p[x][y][k^v];//这是k^v就是我们要求的另一个数，v^v^k=k
return;
}
for(int i=0;i<2;++i)
{
int nx=x-dx[i];
int ny=y-dy[i];
if(nx>=1&&ny>=1) dfs2(nx,ny,v^a[nx][ny]);
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) cin>>a[i][j];
dfs1(1,1,a[1][1]);//左一半
dfs2(n,m,a[n][m]);//右一半
cout<<s;
return 0;
}
双向广搜
其实就和折半搜索差不多，只不过用于广搜。
具体步骤如下：
1. 处理起点和终点
2. 枚举状态
3. 判断起点是否走到了终点走过的地方或判断终点是否走到了起点走过的地方
上个伪代码
void bfs()
{
queue<node>q;
//处理起点和终点
while(!q.empty())
{
node now=q.front();
q.pop();
for(/*枚举状态*/)
{
if(/*满足条件*/)
{
if(/*从起点来*/) vis[nx][ny]=1;//如果vis[nx][ny]=2那就找到了答案
if(/*从终点来*/) vis[nx][ny]=2;//如果vis[nx][ny]=1那就找到了答案
}
}
}
}
迭代加深搜索（IDDFS）
我们发现如果搜索的最大深度很深，而答案却在较左的深度比较浅的为之，这是可以用迭代加深搜索
我们可以每次限制搜索深度，每次到达这个限制深度就结束：
下面给一个伪代码
void dfs(int x,int y)
{
if(x==y) return;//到达限制深度
//do something
}
int main()
{
//do something
for(int i=1;i<=/*最大深度*/;++i) dfs(1,i);
return 0;
}
启发式搜索（A*）
启发式搜索有个估价函数 f(i) = g(i) + h(i)
g(i) 是已花费的代价， h(i) 是将来估计的代价（一定要 ≤ 最小代价）
f(i) 已经不满足的时候就可以return;。
给出伪代码
int h()
{
//要乐观估价（一定要 $≤$ 最小代价）
//do something
}
void dfs(int x,int s)//s是目前代价
{
//ans是目前的最小答案
if(s+h(/*传入状态*/)>=ans) return;
//do something
}
启发式迭代加深搜索（IDA*）
顾名思义迭代加深搜索和启发式搜索结合版。
下面推荐一些题目
dfs： P2066，P1036，P1025。
bfs： P1476，P1162，P1126
dfs 剪枝： P10483，P1731，P1380
折半搜索：P4799，P3067
IDA*： P2324
后记
请注意搜索一般不会成为题目的正解，但是不要以为搜索不重要，搜索可以帮你在比赛中拿到很多部分分，还可以用于对拍你的代码。
