目录
总结
今天听了学长讲的东西之后自己又认真梳理了一下，并且做出了一个最简单的走迷宫题目，（虽然很简单），但是这次真的理解了。
dfs的应用（模板）
（1）走迷宫问题（结合回溯算法）
（2）检验连通性的问题（求联通分量）
举例：
1、迷宫问题
题目：
有一个n*m的迷宫，迷宫中有一些障碍，问你是否有从起点（sx,sy）到终点（fx,fy）的路线，‘&’代表可走的路，‘#’代表障碍不可通过，‘@’代表起点，‘=’代表终点,只可以上下左右的移动
4 5
@&###
#&&&#
#&&&&
##&&=
思想：
有个模拟上下左右移动的数组s[4][2]={
{-1,0},{1,0},{0，-1},{0，1}};有个存放地图信息的数组mp，和标记走没走过的数组vis，vis在搜索过程中可以防止来回移动造成死循环
而且在搜完一种状态后，要回溯，不然搜索的初始条件就发生了改变，结果可能会不对
从起点开始上下左右的搜
dfs函数：
2、连通块问题
题目：
有个n*m的01矩阵，矩阵中只有0和1两种数字，如果一个0上下左右有0则把这些0视为同一个块，问你这个矩阵中有多少这样的块
输入
4 5
0 0 0 1 1
1 1 1 0 0
1 1 1 0 0
1 0 1 0 1
输出 3
思路：
我们可以遍历这个矩阵，当遍历到0时，我们可以从这个坐标开始上下左右搜索，把搜索到的0全部赋为1，应为这些0都是同属于一个块的，当搜完时，块的数量+1
dfs函数：
dfs 应用实验
题目：
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
输入：
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出：
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
样例：
：输入 #1
2 2 1 1 1 2 2 1 2
输出 #1
1
代码实现：
#include<stdio.h>
int sum=0;//计数
int n,m,t;
int sx,sy,fx,fy;
int a[10][10]={0},b[10][10]={0};//数组a记录图，数组b记录走没走过
int s[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//向上下左右走
void dfs(int x,int y)//深搜函数
{
if(x==fx&&y==fy)//走到终点
sum++;
int xx,yy;
for(int i=0;i<4;i++)//判断四种路径
{
xx=x+s[i][0];
yy=y+s[i][1];
if(xx<1||yy<1||xx>n||yy>m||a[xx][yy]==1||b[xx][yy]==1)
continue;//边界或者障碍点或者走过
b[xx][yy]=1;//走过
dfs(xx,yy);//继续搜索
b[xx][yy]=0;//回溯
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
while(t--)
{
int tx,ty;
cin>>tx>>ty;
a[tx][ty]=1;
}
b[sx][sy]=1;//标记起点
dfs(sx,sy);
cout<<sum;
return 0;
}
快排（分区交换排序）
算法描述：
给出一个temp值（默认为数组第一个位置上的数），从数组开头 i 开始找大于temp的数，数组末端 j 开始找小于temp的数，找到之后两位置上的数进行交换，然后(i++,j–)继续找后面小于temp，前面大于temp的数进行交换，直到i=j；把基准点移到i位置，对基准点左右子序列分别进行递归，以此类推，最后得到一个排序好的数组。🐏🐏🐑
图片模拟：
代码实现：
#include<stdio.h>
int a[100],n;
void fun(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left];
i=left;j=right;
while(i!=j)
{
while(a[j]>=temp&&i<j)
j--;
while(a[i]<=temp&&i<j)
i++;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
fun(left,i-1);
fun(i+1,right);
}
int main()
{
int t;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
fun(1,n);
for(int i=1;i<=n;i++)
printf("%d",a[i]);
getchar();getchar();
return 0;
}