深度优先搜索（dfs）

深度优先搜索（Depth-First-Search）是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
对于上述图像中的数据，我们可以对其进行dfs方式的全面搜索，首先以a为顶点，从顶点开始，将一个支路走完再走下一条路，搜索过程为
a-b-e、a-b-f、a-b-c、a-d-g
即是一种不撞南墙不回头的搜索方式。
通过对深度优先搜索的掌握，我们首先可以用其进行对n个数字进行全排列，比如输出1-3的所有排列方式
设想我们有3个卡片分别为1.2.3，以及三个纸箱记为1.2.3。那么所有的卡片放入纸箱的情况即为全排列
那么我们先把1放入1号箱子，2放入2号箱子，3放入3号箱子。这是第一种情况
随后我们可以把3从3号箱子取出，然后发现没有新的情况，于是我们可以把2从2号箱子取出，这时就有了新的放法，我们把3放入二号箱子，把2放入三号箱子，新的放法出现。
这时我们需要再次取出卡片来找到新的放法，我们取出2.3号卡，依然不行，于是我们从1号箱子取出1号，放入2号，随后二三号箱子放入1.3卡片，新的放法又出现了
以此类推，直到全排列
排列顺序为
1-2-3
1-3-2
2-1-3
2-3-1
3-1-2
3-2-1
实现代码如下：

#include<bits/stdc++.h>
using namespace std;
int  n,step,a[1000],book[1000];  //a是排列的数组，book是用来判断第n个数字是否已经被使用 
void dfs(int step)  //深度优先搜索函数，排列第step号箱子
{
	if(step==n+1)  //当轮到排列第n+1个数时，即前n个排列完成，即已经全部填满
	{
		for(int i=1;i<=n;i++)
		printf("%d ",a[i]);  //对数组a进行输出
		printf("\n");
		return;  //这个return会将函数返回上一个dfs
	}
	for(int i=1;i<=n;i++) 
	{
		if(book[i]==0)  //如果数字i还没有使用过
		{
			a[step]=i;  //将i放入第step号箱子
			book[i]=1; //同时将i标记为使用过
			dfs(step+1); //step排列完成，开始排step+1
			book[i]=0; //这里是dfs(step+1)全部结束后，将数字i复原，准备换个数字（即i+1）放入step箱子进行新一轮递归。（理解）
		}
	}
	return;
}
int main()
{
	scanf("%d",&n);
	dfs(1);
	return 0; 
} 

我们将程序运行，输入3

发现规律和我们推导的一致
那现在我们可以尝试看题

题目描述

这有一个迷宫，有0-8行和0-8列：

1,1,1,1,1,1,1,1,1

1,0,0,1,0,0,1,0,1

1,0,0,1,1,0,0,0,1

1,0,1,0,1,1,0,1,1

1,0,0,0,0,1,0,0,1

1,1,0,1,0,1,0,0,1

1,1,0,1,0,1,0,0,1

1,1,0,1,0,0,0,0,1

1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，
问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，
如：从（3，1）到（4,1）。）

输入格式

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）
分别表示起点的行、列，终点的行、列。

样例

输入

2
3 1 5 7
3 1 6 7

输出

12
11

分析

我们可以使用dfs的思想来解决这题，从一个点出发，尝试所有的走法，输出最小的
代码如下：

#include<bits/stdc++.h>
using namespace std;
int mmap[9][9]={ {1,1,1,1,1,1,1,1,1},
				{1,0,0,1,0,0,1,0,1},
				{1,0,0,1,1,0,0,0,1},
				{1,0,1,0,1,1,0,1,1},
				{1,0,0,0,0,1,0,0,1},
				{1,1,0,1,0,1,0,0,1},
				{1,1,0,1,0,1,0,0,1},
				{1,1,0,1,0,0,0,0,1},
				{1,1,1,1,1,1,1,1,1} },next[4][2]={{1,0},{-1,0},{0,1},{0,-1}},x,xx,y,yy,step=0,minn=999999;//打印地图，next为下一次的前后左右走法
void dfs(int x1,int x2,int y1,int y2,int step)
{
	if(x1==x2 && y1==y2) //如果已经在终点，判断步数
	{
		if(step<minn)
		minn=step;
		return;
	}
	for(int i=0;i<4;i++)
	{
		x1+=next[i][0];
		y1+=next[i][1];
		if(x1<0 || x1>7 || y1<0 || y1>7)
		{
			x1-=next[i][0];
			y1-=next[i][1];
			continue;
		}
		if(mmap[x1][y1]==1)
		{
			x1-=next[i][0];
			y1-=next[i][1];
			continue;
		}
		if(mmap[x1][y1]==0)
		{
			mmap[x1][y1]=1;
			dfs(x1,x2,y1,y2,step+1);
			mmap[x1][y1]=0;
			x1-=next[i][0];
			y1-=next[i][1];
		}
	}
	return;
}
int main()
{
	
	int n;
	scanf("%d",&n);
	while(n--)
	{
		minn=999999,step=0; 
		scanf("%d%d%d%d",&xx,&yy,&x,&y);
		dfs(xx,x,yy,y,step);
		printf("%d\n",minn);
	}
	return 0;
}