走迷宫问题是深度优先搜索的一个典型应用，通常迷宫的形状如下
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; }输出结果
