深搜是作为一种遍历或搜索图和树的算法。
思想：不撞南墙不回头！

首先选取一个未访问的点作为源节点。从源节点选取一条路一直往下走，沿着当前顶点的边，访问这条路线，直到走不下去为止。这时返回上一顶点，继续试探访问此顶点的其余子顶点，直到当前顶点的子顶点都被访问过，那么，返回上一顶点，继续重复。从而实现遍历。

来个简单的例子模拟DFS的过程：
（首先，我们默认优先选择靠左或靠下的元素进行访问 ）

选择A作为源节点------>（继续下一层深搜）访问到了B------->（继续下一层深搜）访问到了D------>（继续下一次深搜）搜索到了C------>(此时发现C的所有下一节点都已经被访问过了）返回C的上以节点D（因为是从D访问到C来的，所以不要走回到C的其他上节点）------>我们再遍历D的其他子节点E------->（发现E没有子节点）返回上一节点D------>（发现D没有未被访问的子节点）返回B------>(B没有被访问的子节点）返回A------>（A没有未被访问的子节点）DFS完毕
因此，此图的深搜遍历顺序：A—>B—>D—>C—>E

总结深搜的思路：沿着某条路径遍历，直到末端，然后回溯，再遍历另一条路径（走没有走过的岔路口）做同样的遍历，直到所有的节点都被访问，即回溯到源节点并且源节点已无未被访问的子节点。
举个例子：数的全排列问题，输入一个数n，输出1-n的全排列。
做如下分析：

我们把问题抽象：也就是说，有1-n个数字，要分别放到固定一列的n个盒子里，问分别有哪些不同的放法。

采用深搜的思想（不撞南墙不回头）：
首先我们默认优先放置最小的小数字-----这步相当于选择先走靠左或靠下的路。
开始放置：1放在第一个，2放在第二个···n放在第n个，这样我们已经走到了头，所有的盒子我们都放过数字了。回溯一步并把第n个盒子里的数字n取出，我们当前处于第n-1个盒子处。当前盒子放的是n-1这个数字，我们把它取出来。这时，我们手里有n-1和n两个数字。采用最小数放置原则，但是数字n-1当前刚从这个盒子里取出来。为了避免重复，就不能再放进去了。所以，将目前未放置的数中除了n-1之外的最小数n放入第n-1个盒子里面，再往下走，走到了第n个盒子，手里剩下了一个数字n-1，自然放入第n个了。
此时我们已经拥有了两种排列：
1，2，3，···，n-1，n 和 1，2，3，···，n，n-1
继续回溯：当前在第n个盒子，回溯走到了第n-1个盒子（并取出了第n个盒子里的数字n-1），我们发现这两数字都在第n-1盒子放过，那就只能再回溯了（顺便拿起第n-1个盒子的数字n），走到了第n-2个盒子上，取出这个盒子的数n-2。当前，我们的状态时，在第n-2盒子上，手里有数字，n-2，n-1，n；那么遵循放小原则，并且不能重复，把n-1这个数字放入n-2这个盒子中，继续往下走，先把n-2放入第n-1盒子里，故第n个盒子放数字n了。
此时又出现了一种排列：
1，2，3，···，n-1，n-2，n;
再次从第n盒子回溯到n-1盒子：同理产生了 1，2，3，···，n-1，n，n-2 排列
因为不能往下走了，只能再次回溯到第n-2个盒子，放入n，········
不断重复如上操作，终会回溯到第一个盒子，第一个盒子把最大的数字n都放完之后，再次回溯到第一个盒子，第一个盒子已经无法放别的数字了。那便是全排列结束。

完整代码：

#include <stdio.h>
int a[51][52];//地图 
int book[52][52];//标记 
int n,m,p,q,min=99999999;//m,n为地图大小，p,q为终点，min表示最短距离 
void  dfs(int x,int y,int  step)//当前状态
{
	int next[4][2]={{0,1},//向右 
					{1,0},//向下 
					{0,-1},//向左 
					{-1,0}};//向上
	int tx,ty,i;
	 
	//判断边界条件
	if(x==p&&y==q){//走到了终点 
		if(step<min){
			min=step;
		} 
		return;//返回上一步
	}
	//尝试每一种可能(枚举四种走法) 
	for(i=0;i<4;i++){
		//计算下一点坐标 
		tx=x+next[i][0];
		ty=y+next[i][1];
		//判断是否符合条件（下一点坐标是否超范围，是否是障碍物或已在路径中） 
		if(tx<1||ty<1||tx>n||ty>m){//超范围，则continue下一种走法 
			continue; 
		}
		//可以思考一下为何不把超范围和下一个判断条件放在一起呢 ？？？ 
		if(book[tx][ty]==0&&a[tx][ty]==0){//是否是障碍物或已在路径中,0代表通畅，1代表障碍 
			book[tx][ty]=1;//标记 
			//继续走下一步
			dfs(tx,ty,step+1);
			book[tx][ty]=0;//消除标记 
		} 
		
	}
	return;//全部遍历做完后返回
}
int main(){
	int i,j,sx,sy;//i,j用于循环，sx，xy表示初始坐标
	scanf("%d %d",&n,&m);//输入地图大小
	//读入迷宫地图 ,0代表通畅，1代表障碍 
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	} 
	scanf("%d %d %d %d",&sx,&sy,&p,&q);//输入起始和结束坐标
	book[sx][sy]=1;//起点已经在路径中 
	dfs(sx,sy,0);//从起点深搜 
	printf("%d",min); 
	return 0 ;
}

————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
                        
原文链接：https://blog.csdn.net/Huberyxiao/article/details/105017214