走迷宫问题是深度优先搜索的一个典型应用，通常迷宫的形状如下
0为可走的道路，1为墙壁。通常情况下一些变种的模型，会加入一些特殊项，有别的意思，比如数字5代表钥匙，当然复杂模型先不讨论，从最简单的开始。
深度优先搜索的思想其实就是枚举式的递归，不断的对当前状态下进行对下一状态转移的进行枚举，直到找到解。在迷宫问题中，任意一个可以走的点都有4种转移状态（往上，往下，往左，往右），当然不是每一种状态的转移都是合法的，比如，以左上角（假设）点为起点，起点状态无法转移到：上，左，右这三种状态。只有往下是可以进行转移的，当我们往下转移时，转移时合法的，就递归进一层，此时，我们在新的状态下，重复进行枚举可转移状态并进一步递归进去，然后对合法的状态进行递归来搜索解，当搜索到某一状态搜索完所有可转移的状态时依然无法找到解，就进行回溯到上一层状态，递归转移到下一状态。
深度优先搜索可以用树的前序遍历来理解，我们一直往深处走，走到头了就往回走，然后选则另外一条路继续往深处走，直到全部走完或这找到我们要的条件
下面结合代码来理解
#include<iostream>
#include<math.h>
#include<memory.h>
#include<stack>
using namespace std;
//这是设定的状态转移变量，分为上下左右4组，每一组的值分别代表X,Y的偏移
int dst[4][2]={//上下左右
-1,0,
1,0,
0,-1,
0,1
};
//迷宫，终点设置为数字3，已经走过的节点设置为4
int maze[5][5] = {
0,1, 0, 0, 0,
0,1, 0, 1, 0,
0,0, 0, 0, 0,
0,1, 1, 1, 0,
0,0, 0, 1, 3,
};
void dfs(int x,int y)
{
if(maze[x][y]==3)//判断是否走到了终点，走到了就是输出找到的解
{//if里面是对可行解的一个判断表达式，里面的话就执行我们得到一个解后要进行的操作。
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
cout<<maze[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
return ;
}
for(int i=0;i<4;i++)//枚举转移状态
{
int nextx = x+dst[i][0];//计算转移状态
int nexty = y+dst[i][1];
//下面这里就是DFS的核心部分了，判断转移是否合法，合法的递归进去，不合法的，不进行搜索，if需要包含全部判断条件，不可缺一，否则搜索回出问题
if(nextx>=0 && nextx<=4 && nexty>=0 && nexty<=4&&(maze[nextx][nexty]!=1)&&(maze[nextx][nexty]!=4))//判断下一个要走的点是否合法，在迷宫的题目里面主要是判断转移的点能不能走
{
maze[x][y] = 4;//设置当前点为走过
dfs(nextx,nexty);//进一步搜索
maze[x][y] = 0;//退出来设置为没有走过，这样在回溯进行后续搜索时，不会影响对路径的搜索
}
}
return ;
}
int main()
{
dfs(0,0);//初始调用
return 0;
}输出结果 