//深度优先算法
    //i第一次就是0
    public void dfs(boolean[]isVisited,int i){
        //首先我们访问该节点
        System.out.println(getValueByIndex(i));
        isVisited[i]=true;
        int w=getFirstNeighbor(i);
        while (w!=-1){
            if(!isVisited[w]){
                dfs(isVisited,w);
            }
            //如果w节点已经被访问过
            w=getNextNeighbor(i,w);
        }
    }


    //对dfs进行重载，遍历我们所有的节点，并进行dfs
    public void dfs(){
        //遍历所有的节点，进行dfs,回溯
        for (int i = 0; i < getNumofEdges(); i++) {
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }

    }

基本概念
 
 
 
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
 
 
算法思想
 
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 
 
 
 
 
基本模板
 
int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}

void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}   
 
问题示例
 
1、全排列问题
 
//全排列问题
#include<stdio.h>
#include<string.h>

int n;
char  a[15];
char re[15];
int vis[15];
//假设有n个字符要排列，把他们依次放到n个箱子中
//先要检查箱子是否为空，手中还有什么字符，把他们放进并标记。
//放完一次要恢复初始状态，当到n+1个箱子时，一次排列已经结束
void dfs(int step)
{
    int i;
    if(step==n+1)//判断边界
    {
        for(i=1;i<=n;i++)
            printf("%c",re[i]);
        printf("\n");
        return ;
    }
    for(i=1;i<=n;i++)//遍历每一种情况
    {
        if(vis[i]==0)//check满足
        {
            re[step]=a[i];
            vis[i]=1;//标记
            dfs(step+1);//继续搜索
            vis[i]=0;//恢复初始状态
        }
    }
    return ;
}

int main(void)
{
    int T;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));//对存数据的数组分别初始化
        scanf("%s",a+1);
        n=strlen(a+1);
        dfs(1);//从第一个箱子开始
    }
    return 0;
}
 
2、一个环由个圈组成，把自然数1，2，…，N分别放在每一个圆内，数字的在两个相邻圈之和应该是一个素数。 注意：第一圈数应始终为1。
 
input: N(0~20)
 
output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。
 
//Prime Ring Problem
//与上面的全排列问题其实思路差不多，只是需要判断的条件比较多
//化大为小

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int book[25];
int result[25];
int n;
int num;
//判断是否为素数
int prime(int n)
{
    if(n<=1)
        return 0;
    int i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
            break;
    }
    if(i*i>n)
        return 1;
    return 0;
}
//判断是否能将当前的数字放到当前的圈内
int check(int i,int step)
{
    if((book[i]==0) && prime(i+result[step-1])==1)
    {
        if(step==n-1)
        {
            if(!prime(i+result[0]))
                return 0;
        }
        return 1;
    }
    return 0;
}

void dfs(int step)
{
    if(step==n)//判断边界
    {
        int a;
        printf("%d",result[0]);
        for(a=1;a<n;a++)
        {
            printf(" %d",result[a]);
        }
        printf("\n");
        return ;
    }
    int i;
    for(i=2;i<=n;i++)//遍历每一种情况
    {
        if(check(i,step))//check是否满足
        {
            book[i]=1;//标记
            result[step]=i;//记录结果
            dfs(step+1);//继续往下搜索
            book[i]=0;//恢复初始状态
        }
    }
}

int main(void)
{

    while(scanf("%d",&n)!=EOF)
    {
        num++;
        memset(result,0,sizeof(result));
        memset(book,0,sizeof(book));
        result[0]=1;
        printf("Case %d:\n",num);//格式比较容易出错
        dfs(1);
        printf("\n");
    }
    return 0;
}
 
3、油田问题
 
问题：GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油，并把这个大区域分成了很多小块。他们通过专业设备，来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻，那么他们被认为是同一油藏的一部分。在这块矩形区域，可能有很多油藏。你的任务是确定有多少不同的油藏。
 
input: 输入可能有多个矩形区域（即可能有多组测试）。每个矩形区域的起始行包含m和n，表示行和列的数量，
 
1<=n,m<=100，如果m =0表示输入的结束，接下来是n行，每行m个字符。每个字符对应一个小方格，并且要么是’*’，代表没有油，要么是’@’，表示有油。
 
output: 对于每一个矩形区域，输出油藏的数量。两个小方格是相邻的，当且仅当他们水平或者垂直或者对角线相邻（即8个方向）。
 
//A - Oil Deposits 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char a[105][105];
int n,m,result;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8个方向

int check(int x,int y)//检查是否有油田
{
    if(x>=0&&x<m&&y>=0&&y<n&&a[x][y]=='@')
        return 1;
    return 0;
}

int dfs(int x, int y)
{
    int i,xx,yy;
    if(check(x,y))
    {
        a[x][y]='.'; //统计之后就可以把该油田标记，且不用恢复（要不会重复），
                    //也可以用一个数组来存每个点的访问情况，但是感觉没必要，浪费空间
        for(i=0;i<8;i++)
        {
            xx=x+dir[i][0];
            yy=y+dir[i][1];
            dfs(xx,yy);//依次检查8个方向
        }
        return 1;
    }
    return 0;
}

int main(void)
{
    int i,j;
    while(scanf("%d %d",&m,&n)==2)
    {
        if(m==0&&n==0)
            break;
        result = 0;
        memset(a,0,sizeof(a));
        for(i=0;i<m;i++)
            scanf("%s",a[i]);
        for(i=0;i<m;i++)//在每一个点都搜索一次
        {
            for(j=0;j<n;j++)
            {
                if(dfs(i,j))//找到油田就可以将结果加1
                    result++;
            }
        }
        printf("%d\n",result);
    }
    return 0;
}
 
4、棋盘问题
 
问题：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
 
input： 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
 
output：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int n, k, ans;
char str[10][10];
int vis[100];

void dfs(int r, int k)
{
    if(k==0)//判断边界，此时棋子已经放完
    {
        ans++;
        return;
    }

    for(int i=r; i<n; i++)//每次都从放过棋子下一行开始搜索，保证不重复
    {
        for(int j=0; j<n; j++)
        {
            //循环保证行不重复，check保证列不重复
            if(str[i][j]=='.' || vis[j]==1)
                continue;//不满足条件直接跳过
            vis[j] = 1;//标记
            dfs(i+1, k-1);//继续下一次标记
            vis[j] = 0;//恢复初始状态
        }
    }
}

int main(void)
{
    while(1)
    {
        scanf("%d %d", &n, &k);
        getchar();
        if(n==-1 && k==-1) 
            break;
        memset(str, '\0', sizeof(str));
        memset(vis, 0, sizeof(vis));
        ans = 0;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
                str[i][j] = getchar();
            getchar();
        }

        dfs(0, k);//从第0行开始放，此时手中还剩k个棋子
        printf("%d\n", ans);
    }
    return 0;
}
 
参考文章
 
https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox
 
https://blog.csdn.net/qq_42815188/article/details/89258074
 
https://www.jianshu.com/p/5cda08b4b391

前言
 
看了许多的关于dfs的博客，自己也研究了好多遍，最终算是入门了，下面就简单的个人理解的原理以及结合一个简单的全排列实例进行讲解。
 
原理简介
 
DFS基于递归思想，递归思想就是把一个事拆分成若干见相同的小事共同组合完成，具体见下图的斐波那契的图文解决
 
 这就是一个最典型的递归，入口f(5)出口就是每次递归的return；
 说完递归就是dfs，其有两个重要的标志，也就是两个数组，一个用来标记该点是否被访问过，一个用来把该点放入数组，所以这两个标记是相辅相成的，一定同时出现；dfs就是随机选定一个起点将其标记为已经访问过的点，然后就是递归调用进行与其相邻的点的搜索，直到所有的点都被访问完。
 话不多说上例子
 全排列，也就是1-n，输出其所有的排列结果。
 代码如下，接下来会详细解读代码：
 
#include <stdio.h>
#include <iostream>
using namespace std;
int a[101],b[101],n;
void print()
{
	int i;
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	cout<<endl;
}
inline void dfs(int i) 
{
	int j;
	if(i==n+1)
	{
		print();
		return;
	}
	for(j=1;j<=n;j++)
	{
		if(b[j]==0)
		{
			a[i]=j;
			b[j]=1;
			dfs(i+1);
			b[j]=0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	dfs(1);
	return 0;
}

 
注：以上代码来自csdn博客 Apro1066。
 这个代码看上去不多，但是确实经典，有好多值得推敲的东西。
 首先主函数中的dfs(1)这是dfs函数进入，传入参数1就是从1开始，主要在dfs函数的理解，下面的图片展示了展示了这个过程。
 
 
下面是一个DFS的经典问题-走迷宫,大家可以结合代码做进一步的理解。
 
 
Code
 
#include<bits/stdc++.h>
using namespace std;
bool a[101][101]={0};
char b[101][101];   //存放迷宫 
int flag=0;     //如果能走出去就标记为1，反之为0
int xx[4]={0-1,0,1},yy[4]={-1,0,1,0};
int n,kx,ky;   //n是迷宫的边长，kx是x进行加减之后的值，同理ky。 
void dfs(int x,int y){
	for(int i=0;i<=3;i++){
		kx=x+xx[i];
		ky=y+yy[i];
		if((b[kx][ky] == '.'||b[kx][ky] == 'e')&&kx>=0&&ky>=0&&kx<n&&ky<n&&a[kx][ky]==0){
			a[kx][ky]=1;
			if(b[kx][ky] == 'e'){
				flag = 1;
			}else{
				dfs(kx,ky);
			}
		}
	}
}

int main(){
	int k=1,sum;
	cin>>sum;
	while(k<=sum){
		memset(a,0,sizeof(a)); //将标记数组a全部记为 0，表示这个点未走过 
		cin>>n;
		for(int i = 0;i<n;i++){
			for(int j=0;j<n;j++)
				cin>>b[i][j];
		}
		for(int i = 0;i<n;i++){
			for(int j=0;j<n;j++){
				if(b[i][j]=='s')
					dfs(i,j); 
			}
				
		}
		if(flag==1){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
		k++;
	}
	return 0;
} 
 
有不懂的地方或者有错误的地方欢迎评论批评指正。

 
DFS史诗级入门教程
 
DFS
1.全排列（入门引导）
1.1排列方法
1.2程序理解
1.3基本模型
   
2. 拓展（全排列）
2.1思路
2.2源码
   
3.迷宫问题
3.1思路
3.2完整源码
   
4.题目实践
 

 
DFS
 
最近一直都在写蓝桥杯的题目，其中有许多题目涉及到了搜索（DFS，BFS）等，由于递归过于抽象，所以没能很好的掌握。于是便写下了这篇入门教程来加深对DFS的认识，并且充分理解递归。
 所谓DFS就是指：优先考虑深度，换句话说就是一条路走到黑，直到无路可走的情况下，才会选择回头，然后重新选择一条路。
 
1.全排列（入门引导）
 
 
 
引导题：输入一个数n，输出n的全排列
 可以先把这个问题形象化
 如：
 
 
 
  
假如有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。将这3张扑克牌分别放入3个盒子一共有几种不同的放法呢？
 
 
 
 
1.1排列方法
 
约定：
 
 
 
每次到一个盒子面前时，都先放1号，2号，最后放3号
 
 
1.第一种：
 

 首先呢，小明手中有3张扑克牌，先到第1个盒子，将1号扑克牌放在第1个盒子。
 
 
放好后，小明继续向前走一步，来到了2号盒子，按照之前的约定放2号扑克牌。
 

 放好后，小明又继续向前一步，把3号扑克牌放入3号盒子。此时就已经完成了一种排列。
 
 
完成第一种后,还没有结束！小明便要回头了，开始重新选择（DFS的思想），这里要注意的，不是把所有的牌都取出来重新放，这样就不符合DFS的思想了。
 
2.第2种
 好的！按照上面的逻辑。小明将3号盒子的3号扑克牌取出，但手上仍然只有3号扑克牌。
 所以小明只好回到2号盒子，收回2号扑克牌，此时手中有2,3号扑克牌。
 按照之前的约定，往2号盒子放3号扑克牌，然后小明又继续往前走，此时手里只有2号扑克牌，把2号扑克牌放入3号盒子里，此时完成了第二种排序。*
 按照这种逻辑，我们不难求出所有排列“123”，“132”，“213”，“231”，“312”，“321”
 
1.2程序理解
 
说了这么多，应该对DFS有了大概的了解吧。下面用程序来加深大家对DFS的认识。
 可能大家会有疑惑，怎么才能往小盒子里放扑克牌呢？
 其实很简单，只需要一个for循环就行了。
 
for(int i=1;i<=n;i++)
	a[step]=i;
	//将i号扑克牌放到第step个盒子中
 
这里的数组a是用来表示盒子的，变量step表示当前处于第step个盒子面前。
 这里还有一个问题：如果一张扑克牌已经放入别的盒子里了，该怎么样才能使这张扑克牌不放到当前的盒子里。
 其实很简单，只需要再重新创建一个数组book用来标记，看扑克牌是否被使用。
 
for(int i=1;i<=n;i++){
	if(book[i]==0){   
	//说明i号扑克牌还在手里，需要放入step号盒子
	a[step]=i;
	//将i号扑克牌放到第step个盒子中
	book[i]=1;
	//此时i号扑克牌已经被使用
		}
	}
 
那么接下来如何表示step+1呢？难道要一个函数一个函数这样写吗？其实不需要这么麻烦。
 只需要把处理第step的代码封装成一个函数就可以了。
 
void  dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌
	for(int i=1;i<=n;i++){
	if(book[i]==0){   
	//说明i号扑克牌还在手里，需要放入step号盒子
	a[step]=i;
	//将i号扑克牌放到第step个盒子中
	book[i]=1;
	//此时i号扑克牌已经被使用
		}
	}
}
 
接下就是处理第step+1的具体代码了
 
void  dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌
 for(int i=1;i<=n;i++){
	if(book[i]==0){   
	//说明i号扑克牌还在手里，需要放入step号盒子
	a[step]=i;//将i号扑克牌放到第step个盒子中
	book[i]=1;//此时i号扑克牌已经被使用
		
	dfs(step+1);
	/*注意这里是自己调用自己，表示此时走到了第step+1个盒子面前*/		
	book[i]=0;
	/*book[i]=0表示dfs调用结束了，换句话说就是扑克牌已经全部放完了
	  需要按照顺序将扑克牌收回，重新放，也就是前面所说的
	 */
		}
	}
}
 
说到这里，是不是已经能够理解dfs。现在还要进行最后一步：程序结束的标志和完整的代码
 
#include<stdio.h>
int a[10],book[10],n;
//这里还有需要注意的地方C语言全局变量默认为0

void  dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌
	int i;
	if(step==n+1){    //这里说明前面的n个盒子已经放好了，这是dfs结束的标志 
		for(i=1;i<=n;i++)
			printf("%d",a[i]);
		printf("\n");
		
		return ;
		/* 
		注意这个 return 它的作用不是返回主函数，而是返回上一级的dfs函数
		
		例：如果此时是  dfs(5),遇到这个 return 就会回到上一级的 dfs函数 
		也就是dfs(4),但此时dfs(4)的大部分语句已经执行了，只需要接着执行 book[i]=0
		然后继续进入for循环进入下一次的 dfs函数，直到结束。 		
		*/ 
		
	}
	 for(int i=1;i<=n;i++){
		if(book[i]==0){  //说明i号扑克牌还在手里，需要放入step号盒子
			a[step]=i;//将i号扑克牌放到第step个盒子中
			book[i]=1;//此时i号扑克牌已经被使用		
			dfs(step+1);
			/*注意这里是自己调用自己，表示此时走到了第step+1个盒子面前*/		
			book[i]=0;
			/*book[i]=0表示dfs调用结束了，换句话说就是扑克牌已经全部放完了
			  需要按照顺序将扑克牌收回，重新放，也就是前面所说的
			 */
		}
	}
	return;//这里表示这一级别的dfs函数已经结束了，返回上一级 dfs函数 

}
int main(){
	scanf("%d",&n);
	dfs(1);   //dfs函数的开始 
	return 0;
}
 
相信大家已经能理解dfs了吧。其实要理解dfs的关键在于解决“当下该怎么做”和“下一步如何做” 。下面便是dfs的基本模型，基本大部分的dfs题目都能按照此模型来写。
 
1.3基本模型
 
void dfs(int step){
	判断边界
	尝试每一种可能 for(i=1;i<=n;i++){
		继续下一步 dfs(step+1)
		}
	返回
}
 
2. 拓展（全排列）
 
 
 
1-9 9个数凑一个等式，其中每个数由3个数字组成
 
 
 
2.1思路
 
初看这个题目，其实最容易想到的其实是暴力枚举，如果用暴力枚举的话，则需要用到9重for循环，而且每个数都不能相同。在这里就不用这种方法了。
 接下来就来看看dfs的用法吧
 
2.2源码
 
#include<stdio.h>
int a[10],book[10],total;
//这里还有需要注意的地方C语言全局变量默认为0

void  dfs(int step){ 
	int i;
	if(step==10){ 
		if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9]){
			total++;
			printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
		} 	
	return ;   
}		
	 for(int i=1;i<=9;i++){
		if(book[i]==0){  //说明i号扑克牌还在手里，需要放入step号盒子
			a[step]=i;//将i号扑克牌放到第step个盒子中
			book[i]=1;//此时i号扑克牌已经被使用		
			dfs(step+1);
			/*注意这里是自己调用自己，表示此时走到了第step+1个盒子面前*/		
			book[i]=0;
			/*book[i]=0表示dfs调用结束了，换句话说就是扑克牌已经全部放完了
			  需要按照顺序将扑克牌收回，重新放，也就是前面所说的
			 */
		}
	}
	return;//这里表示这一级别的dfs函数已经结束了，返回上一级 dfs函数 

}
int main(){
	dfs(1);   //dfs函数的开始 
	printf("%d",total/2);
	return 0;
}
 
3.迷宫问题
 
 
 
题目大概意思：处于迷宫入口的小明（1,1），寻找位于（p，q）的小红，也就是最短路径问题 其中n表示行，m表示列
 
 
 
看到这个题目的时候用DFS，感觉就是四处碰壁，最后才走向成功。也就是指把所有的情况都发生一次，才知道最好的选择并输出。
 
3.1思路
 
首先要把这个迷宫看作一个二维数组，每走一步就相当于x或者y变化
 
 接下来看看如何表示小明走一步吧！其实很简单，只需要用一个二维数组就行了哦。
 
int next[4][2]={
 {0,1), //向右走一步
 {1,0},//向下走一步
 {0,-1},//向左走一步
 {-1,0}};//向上走一步
 
下面的一张图，就更方便大家理解了，正好与上面的源码对应。
 
 通过这个方向数组，使用循环就很容易获得下一步的坐标。这里可以用tx，xy来表示。
 
for(k=0;k<=3;k++){   //下一步的坐标
	tx=x+next[k][0]; //下一步的坐标：当前的+下一步要走的
	ty=y+next[k][1];//下一步坐标：当前的+下一步要走的
}
 
下面来对下一点（tx,ty） 进行一些判断。
 包括是否越界，是否为障碍物，已经这个点是否被访问。所以也要一个book[tx][ty]来记录点是否被访问。如果这个点符合所有要求，就继续寻找下一个点，也就是 dfs( tx,ty,step+1)。
 注意：a[][]等于0表示该点不是障碍
 还有book[][]等于0表示该点还没走过
 下面就是具体的代码
 
for(k=0;k<=3;k++){   //下一步的坐标
	tx=x+next[k][0]; 
	ty=y+next[k][1];
	
	//判断是否越界
	if(tx<1 || tx>n || ty<1 || ty>m)
		continue;  
		//运行到这里，说明这条路，则需要换个方向，也就是重新进入for循环
	if(a[tx][ty]==0 && book[tx][ty]==0){
		book[tx][ty]=1; //标记这个点走过
		dfs(tx,ty,step+1); //进行下一步
		book[tx][ty]=0;   //重新尝试，退回到上一个点的位置
		}
	
}
 
其实到这里也就差不多了，但还有最后一步。如何判断小明已经找到小红了。不多说了，看代码吧！
 
void dfs(int x,int y,int step){   //step用来表示找到小红，小明走了多少步
	if(x==p&& y==q){  //说明已经找到了小红   
		if(step<min)
			min=step;
		return ;   //返回上一步，继续寻找其他路径
		}
	return 0;
	}
 
3.2完整源码
 
#include<stdio.h>
int book[51][51],a[51][51];
int n,m,p,q,min=99999;
	int next[4][2]={
 				    {0,1}, //向右走一步
					{1,0},//向下走一步
					{0,-1},//向左走一步
					{-1,0}};//向上走一步

void dfs(int x,int y,int step){   //step用来表示找到小红，小明走了多少步
	int tx,ty,k;
	if(x==p&& y==q){  //说明已经找到了小红  
	/*
	还要说明一点：这里 为什么是（x，y），而不是（tx，xy） 
	其实很简单 就是上一个dfs()函数传过来的坐标 ，做了这个dfs()函数的形参 
	换句话说：就是判断点是否找到小红 
	*/ 
		if(step<min)
			min=step;
		return ;   
		/*返回上一步，继续寻找其他路径（就是退回到上一个坐标，重新找其他路径）
		   回到上一个dfs()函数 
		
		*/ 
		}
		
	for(k=0;k<=3;k++){   //下一步的坐标
		tx=x+next[k][0]; 
		ty=y+next[k][1];
	
			//判断是否越界,越界则重新进入for循环 
			if(tx<1 || tx>n || ty<1 || ty>m)
				continue;  
				//运行到这里，说明这条路，则需要换个方向，也就是重新进入for循环
			if(a[tx][ty]==0 && book[tx][ty]==0){
				book[tx][ty]=1; //标记这个点走过
				dfs(tx,ty,step+1); //进行下一步
				book[tx][ty]=0;   //重新尝试，退回到上一个点的位置
		}
	
		}
		return ;   //执行到这里，这层dfs()函数已经结束，则要回到上一层dfs()函数 
	}

int main(){
	int i,j,startx,starty;
	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",&startx,&starty);  //小明的坐标 
	scanf("%d %d",&p,&q);            //小红的坐标 
	
	book[startx][starty]=1;         //起始点标记，就不会回到这个点了 
	dfs(startx,starty,0);      //开始寻找最短路径 
	
	printf("%d",min);        //输出最短路径 
	return 0;
}
 
4.题目实践
 
看完这几道题可远远不够哦，接下来，还准备了一些题目加深大家对DFS的认识
 1.蓝桥杯真题题解-剪邮票
 2.蓝桥杯真题题解-方格填数
 3.蓝桥杯真题题解-方块分割
 4.题目链接：P1219 [USACO1.5]八皇后 Checker Challenge
 题解：递归+回溯（DFS）
 5.题目链接：P1596 [USACO10OCT]Lake Counting S
 题解：DFS