本蒟蒻第一次发文章，如有写的不详细或不正确的的请在评论区指出及纠正
那就直接开始正题吧
DFS全称Depth First Search，中文名为“深度优先搜索”，是基于递归的实现的
深搜本质思想：先随意选择某种情况执行，在过程中，一旦发现方案不可用，就马上退回一步重新选择另一种情况，如此重复进行，直到找到解
两个基本框架：
第一种
int fx(int k){
for(int i=1;i<=算符总数;i++){
if(满足条件){
保存结果;
if(到目的地){
输出解;
}
else fx(k+1);
}
恢复:保存结果之前的状态;
}第二种
int fx(int k){
if(到目的地){
输出解;
}
else{
for(int i=1;i<=算符总数;i++){
if(满足条件){
保存结果;
fx(k+1);
恢复:保存结果之前的状态(回溯一步);
}
}
}
}接下来，让我们了解下广搜bfs
BFS全称Breadth First Search，中文名为“广度优先搜索”
广搜本质思想：从初始节点开始，生成第二层节点，检查目标节点是否存在于这一层节点中，如果是，直接输出解，不然就继续生成节点，继续检查是否存在于这一层中......如此反复循环，直到找到解
例如下面这张图......
本画画废柴亲自手绘，不喜勿喷
像上面那张图一样
先生成A2,A3点，检查目标节点是否在里面，如果没有，继续生成A4,A5,A6,A7四个点，继续检查，如果有就输出，没有继续生成...
深搜的优点：代码量少，容易理解，能找出所有解决方案
缺点：非常容易超时！！！！！！！！！
广搜优点：解决最短路等问题特别好用
缺点：内存消耗大
“总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时，要综合考虑。决定取舍。”摘自査佬@haohao_____
看道例题
1255：迷宫问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 12406 通过数: 5777【题目描述】
定义一个二维数组：
int maze[5][5] = { 0,1,0,0,0, 0,1,0,1,0, 0,0,0,0,0, 0,1,1,1,0, 0,0,0,1,0, };它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
【输入】
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
【输出】
左上角到右下角的最短路径，格式如样例所示。
【输入样例】
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0【输出样例】
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
这道题用深搜和广搜都可以做，不过深搜最多只能A 9个点，广搜才能AC
深搜代码
思路：把所有路线枚举出来，选择最短的
#include<bits/stdc++.h>
#define inf 1<<30
using namespace std;
int a[6][6];
int xxx[160][160][6];
int pyx[6]={0,0,1,-1},
pyy[6]={1,-1,0,0};
int ans[160];
int tot;
void dfs(int x,int y,int step)
{
int xx,yy;
if(x==4&&y==4){
ans[tot]=step;
tot++;
return;
}
for(int i=0;i<4;i++)
{
xx=pyx[i]+x;
yy=pyy[i]+y;
if(xx<=4&&yy<=4&&xx>=0&&yy>=0&&a[xx][yy]!=1){
a[xx][yy]=1;
xxx[tot][step][0]=xx;
xxx[tot][step][1]=yy;
dfs(xx,yy,step+1);
a[xx][yy]=0;
}
}
}
int main()
{
for(int i=0;i<=4;i++){
for(int j=0;j<=4;j++){
cin>>a[i][j];
}
}
dfs(0,0,0);
int min=inf,index;
for(int i=0;i<tot;i++){
if(ans[i]<=min) min=ans[i],index=i;
}
cout<<"(0, 0)"<<endl;
for(int i=0;i<min;i++){
cout<<"("<<xxx[index][i][0]<<", "<<xxx[index][i][1]<<")"<<endl;
}
}
广搜代码
#include<bits/stdc++.h>
using namespace std;
int a[6][6];
int pyx[6]={0,0,1,-1},
pyy[6]={1,-1,0,0};//偏移量
struct node{
int x,y,pre;//pre前驱
}p[10001];
void print(int len)//这里运用递归方法，一直递归直到到了最顶层节点
{
if(p[len].pre!=0) print(p[len].pre);
cout<<"("<<p[len].x<<", "<<p[len].y<<")"<<endl;
}
int main()
{
for(int i=0;i<=4;i++){
for(int j=0;j<=4;j++){
cin>>a[i][j];
}
}
int head,tail,xx,yy;
head=0;tail=1;//头指针及尾指针
p[tail].x=0;
p[tail].y=0;
p[tail].pre=0;
while(head<tail){
head++;
for(int i=0;i<4;i++){
xx=p[head].x+pyx[i];
yy=p[head].y+pyy[i];
if(xx>=0&&yy>=0&&xx<=4&&yy<=4&&a[xx][yy]!=1)//判断条件
{
a[xx][yy]=1;//不能走回头路
tail++;
p[tail].x=xx;
p[tail].y=yy;
p[tail].pre=head;
if(xx==4&&yy==4)//输出结果
{
print(tail);
break;
}
}
}
}
}最后安利一下洛谷账号（逃）doge