2020.1.11
做题的时候发现自己还是不太会运用这两种算法，所以决定还是先把它学清楚再做题。
学习方法：看书（啊哈算法），看网站（CSDN，博客园）
DFS（深度优先搜索）
dfs的实现方法：递归。
在深搜的同时考虑回溯，一次把一条路找到底，走完或者走不通再回溯，把所有解都找出来。多用于解决所有解和连通性问题。但他的规模不能太大。搜索的时候有记录走过的位置，标记完后可能要改回来。
回溯法是一种搜索法，按条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法；
dfs还是比较好理解的，但是要在做题的时候灵活运用，把题目转化为简单模型，在模板的基础上做改变。
dfs模板：
void dfs(int step)
{
//判断边界
if（符合某种条件/不能继续搜索了）
{
...
return ;
}
//尝试每一种可能
for(i=1;i<=n;i++)
{
if(符合某种条件)
{
...
dfs(step+1);//递归
...（有时候需要把改变的条件改回来）
}
}
return ；
}
BFS（广度/宽度优先搜索）
bfs的实现方法：队列。（不用自定义一个函数，因为不需要递归，直接在主函数中进行）
分治界限法，一次访问多条路，层层递进，每一层就代表一步，每一层都需要储存大量信息。适合解决最优解，最短路径问题。规模可以比较大。（但dfs也可以解决最短路问题，只不过效率不一样）
从一个点往每个它相邻的点走，然后在从这些路，在找可以走的路，直到最先找到符合条件的，需要用到队列。
用队列模拟过程，用结构体实现队列。
BFS的基本步骤
1. 初始化一个空队列，将初始点（一个或多个）加入一个集合尾
2. 从集合头取出点，判断初始点的周边点，将符合条件的点加入队列
3. 重复 2 操作，直至集合为空。 ( 一般 每个点只加入队列一 次 )
用一个例子来加深对bfs的理解吧（参考书：啊哈算法//我觉得这上面每个步骤讲的很清楚）
题目就是给一个地图，要求起点到终点有多少条路径。不过多赘述了。
首先第一步，”用队列模拟过程，用结构体实现队列“，创建一个空链表，把起点入列。
struct node
{
int x;//横坐标
int y;//纵坐标
int s;//步数
}que[2501];//地图大小不超过50*50，所以队列扩展不会超过2500个
int a[51][51];//储存地图
int book[51][51];//用book数组标记哪些点以及在队列中了，防止一个点被重复扩展。
//tip：全局变量默认所有元素初始化为0
///初始化空队列
int head=1;
int tail=1;
//将起点（1，1）入队，并标记（1，1）已经走过
que[tail].x=1;
que[tail].y=1;
que[tail].s=0;
tail++;
book[1][1]=1;
假设从（1，1）开始，先尝试往右走一步到达了（1，2）。
tx=que[head].x;
ty=que[head].y+1;
此时需要判断扩展点（1，2）是否越界
if(tx<1||tx>n||ty<1||ty>m)
continue;
再判断（1，2）是否为障碍物或者已经在路径中
if(a[tx][ty]==0&&book[tx][ty]==0)
{
}
如果满足以上条件则是我们要找的点，将它（1，2）入队，并标记该点已经走过
if(a[tx][ty]==0&&book[tx][ty]==0)
{
//把这个点标记为已经走过
book[tx][ty]=1;//注意宽搜每个点通常情况下只入队一次，和深搜不同，不需要将book数组还原啦。
//插入新扩展点
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[tail-1].s+1;//步数是父亲的步数+1
tail++;
}
接下来还要尝试往其他方向走。我们发现从（1，1）还可以到达（2，1），因此我们要把（2，1）也入队，代码实现的操作与刚才一样。
这个时候对（1，1）的扩展完毕了，它对我们来说就没用了，做个渣男，用完就丢！此时一招将（1，1）出队。
head++；
接下来我们就在新扩展出来的点的基础上再次扩展，直到达到指定位置（终点），没到达就继续扩展。（1，1）出队之后，队首head就指向了刚才扩展的第一个扩展点（1，2），我们继续通过这个点扩展，把新的扩展点入队，扩展完这个点再把它丢了，扩展下一个点…..这样子。
为了方便向四个方向扩展呢我们可以设置一个老朋友数组了：next数组。
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
捋清楚这些过程，然后把这些操作组合，就得到完整代码啦！如下：
#include<stdio.h>
struct node
{
int x;//横坐标
int y;//纵坐标
int s;//步数
} que[2501]; //地图大小不超过50*50，所以队列扩展不会超过2500个
int a[51][51];//储存地图
int book[51][51];//用book数组标记哪些点以及在队列中了，防止一个点被重复扩展。
//tip：全局变量默认所有元素初始化为0
int main()
{
//定义一个用于表示走的方向的数组
int next[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
//k：用于枚举方向；n，m：地图大小；startx，starty：起点坐标；p，q：终点坐标；tx，ty：扩展点坐标。flag：标记是否到达终点。
//输入地图
scanf("%d %d",&n,&m);
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
scanf("%d",&a[i][j]);
scanf("%d %d %d %d",&startx,&starty,&p,&q);//输入起点和终点坐标
///初始化空队列
int head=1;
int tail=1;
//往队列插入起点坐标
que[tail].x=startx;
que[tail].y=starty;
que[tail].s=0;
tail++;
book[startx][starty]=1;
flag=0;
while(head<tail)//当队列不为空时循环
{
//枚举4个方向
for(k=0; k<4; k++)
{
tx=que[head].x+next[k][0];
ty=que[head].y+next[k][1];
//判断是否越界
if(tx<1||tx>n||ty<1||ty>m)
continue;
//判断是否是障碍物或者已在路径中
if(a[tx][ty]==0&&book[tx][ty]==0)
{
//把这个点标记为已经走过
book[tx][ty]=1;//注意宽搜每个点通常情况下只入队一次，和深搜不同，不需要将book数组还原啦。
//插入新扩展点
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[head-1].s+1;//步数是父亲的步数+1
tail++;
}
if(tx == p&&ty == q)//到达终点则推出循环
{
flag=1;
break;
}
}
if(flag == 1)
{
break;
}
head++;//注意这个地方前往不能忘记，当一个扩展点结束后，head++才能对下一个扩展点进行扩展
}
//打印末尾最后一个点（目标点）的步数
//注意tail是指向队列的队尾的下一个位置，所以需要减一
printf("%d",que[tail-1].s);
return 0;
}
别人说的好！！
（来自博客园：里昂静）//图侵删
