🏆今日学习目标：
🍀1理解搜索思路
🍀2学会搜索模板
✅创作者：贤鱼
🔥深度优先搜索
了解原理
==以深度为优先的搜索算法==，可以理解为一条路走到黑
图例解释
==现在需要从蓝色五角星走到红色五角星
理想走法：
==很明显，这里直走到头已经走不了了，才会从之前的岔路拐弯（一路走到黑）==
==这就是深度搜索走迷宫的全过程==，当然，深度优先搜索不只是光能走迷宫，其他的例题后面会讲
方向数组
一般会定义两个数组
int dx[5]={0,1,-1,0,0}
int dy[5]={0,0,0,1,-1}这里我一般喜欢让数组下标从1开始，所以第一个0只是顶替个位置
for(int i=1;i<=4;i++){
int tx=dx[i]+x;
int ty=dy[i]+y;
}这里xy是原来的坐标，txty是走后的坐标，一般题目要求是上下左右四个方向走，如果要求斜方向也可以走方向数组会有些变化
int dx[8]={0,1,-1,0,0,1,-1,-1,1}
int dy[8]={0,0,0,1,-1,1,-1,1,-1}函数
函数的类型在本章需要的主要有两种：
==int==类型和==void==类型
前者有返回值，可以处理各种类型的题目，后者没有返回值，常用于走迷宫一类的题。
递归
还是看上方的图，只有走到死路的时候会往前走其他的路，这个过程就是递归的过程
🍀套用模板
void dfs(int x,int y){
if(x==xx&&y==yy)//到终点了
return；//void类型返回值为空
for(int i=1;i<=4;i++){
int tx=dx[i]+x;
int ty=dy[i]+y;
if() continue//这里判断有没有出界，有没有走过，有没有碰到墙之类的
//如果没有就继续
vis[tx][ty]=1//记录一下走没走过，避免重复走，如果不记录会死循环，上下上下不停地走
dfs(tx,ty);
}
}🔥广度优先搜索
==以广度为优先的搜索==，可以理解为在每一步的时候处理所有的可能性
还是来看看图：
可以看到这里遇到了岔路
我们在这里同时处理
了解原理
队列
==特点== 先进先出：可以理解为一个联通的钢管，先放进去的部分先掉下来
手打队列
void bfs(){
head=0;tail=1;//这里是记录头和尾的坐标，如果t加1，也就是入队的过程，如果h加1，就是出队的过程
qw[0][0]=1;
a[tail]=0,b[tail]=0;
while(tail!=head){
head++;
for(int i=1;i<=4;i++){//下面部分基本一样
int tx=a[head]+dx[i];
int ty=b[head]+dy[i];
if() continue;
tail++;
a[tail]=tx;//这里入队并且记录数据
b[tail]=ty;
qw[tx][ty]=1;//避免走重复，和上文一样，避免死循环，不过广搜不是很影响
if(到终点){
return;
}
}
}
}queue
struct aaa{
int x,y;
};//记录一下结构体，具体下面有介绍void bfs(){
vis[x][y]=1;
dis[x][y]=0;
queue <aaa> q;//aaa是结构体的类型，这句话的意思是定义一个类型为aaa的队列
q.push((aaa){x,y});//入队的意思，第一个括号写类型，因为结构体是aaa类型，xy是int类型，后面是入队数据
while(!q.empty()){//这句话的意思是当队列不为空（empty是为空的意思，！取反）
aaa a;//定义一个aaa类型的变量a
a=q.front();//这个意思是取出队首元素，也就是队列中最先进去的
q.pop();//取出队首元素后出队，将已经取出的元素扔掉
for(int i=1;i<=4;i++){
int tx=a.x+dx[i];
int ty=a.y+dy[i];
if() continue;
q.push((aaa){tx,ty});//入队的意思，和上文h，t作用一样
vis[tx][ty]=1;//记录路径，避免重复
if(到终点){
return;
}
}
}
return ;
}结构体
struct aaa{
int x,y;
};
aaa a;//定义一个aaa类型的a
a.x;
a.y;这样可以方便记录数据
a[i],b[i];当然，这样子记录xy坐标也是可以的，但是有些麻烦🍀套用模板
void bfs(){
入队
while（队列不为空）{
取出队首元素
出队
for（1 to 4）{
和上文深搜走迷宫一样
如果可以走{
入队元素
}
如果到终点{
return；
}
}
}
}
==🏆结束语== 搜索不光可以走迷宫，其他具体的题目题解可以看到专栏内容
