如果你没有dfs基础，可以先看看我的前2篇文章
C语言递归+DFS（深度优先搜索算法）详解 图文并茂，手把手教你画树状图
C语言dfs深度优先练习 N皇后 图文并茂超详解 ！
一.题目描述
我们先来解决迷宫问题的初级版。（洛谷B3625）
二.图文解析
我们先用一个样例来分析一下迷宫怎么走（灰色阴影代表墙不能走）
。
我们首先需要明白dfs的特点：不撞南墙不回头。对于一条路径，它会从起点一直走到此路不通的位置或者终点。但对于任意一个位置，有上下左右四个方向，程序又该怎么走呢？所以我们需要规定一个顺序->右下左上
准备工作做好了，我们就可以自己模拟程序的思路来走走迷宫了。
（走到一个位置就打勾，标记该位置已经走过，对应代码里该位置的状态设置为1）
像图片这样，我们成功获得了其中一条路径。我们再继续模拟一遍回溯。
（蓝色线代表回溯的过程，回溯到一个位置，该位置就打个半勾—>标记为未走过）
三.代码实现
①我们立马想到dfs的cp——状态数组
在迷宫问题里，状态数组就来存储一个位置到底有没有走过。
int state[101][101] = { 0 };//状态数组，令0代表未走，1代表走了
②怎么实现程序前进的效果呢
每一个位置都对应一个坐标，那么当位置改变，对应的其实就是坐标的改变。
每前进一步，我们只需把下一步的坐标传给dfs函数就行啦
③完整代码
int m,n;
char maze[101][101];//存放输入的迷宫
int state[101][101] = { 0 };//状态数组，令0代表未走，1代表走了
void dfs(int x, int y, int count)
{
if (x == n && y == m)
{
printf("Yes\n");
exit(0);
}
//右
if (maze[x + 1][y] == '.' && state[x + 1][y] == 0)
{
state[x + 1][y] = 1;
dfs(x + 1, y, count + 1);
state[x + 1][y] = 0;
}
//下
if (maze[x][y - 1] == '.' && state[x][y - 1] == 0)
{
state[x][y - 1] = 1;
dfs(x, y - 1, count + 1);
state[x][y - 1] = 0;
}
//左
if (maze[x - 1][y] == '.' && state[x - 1][y] == 0)
{
state[x - 1][y] = 1;
dfs(x - 1, y, count + 1);
state[x - 1][y] = 0;
}
//上
if (maze[x][y + 1] == '.' && state[x][y + 1] == 0)
{
state[x][y + 1] = 1;
dfs(x, y + 1, count + 1);
state[x][y + 1] = 0;
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
getchar();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%c", &maze[i][j]);
}
getchar();//getchar是为了吃掉换行符
}
dfs(1, 1, 0);
printf("No\n");
return 0;
} 四.代码优化—方向数组
观察上方代码，右下左上的代码雷同，不够简洁美观。如何达到简洁的效果呢？我们想到dfs的一个老朋友——for循环。在这里，我们还需根据上方画的方位图，搭配以下的方向数组。
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
//顺时针试探
for (int i = 0; i <=3; i++)
{
int tx, ty;
tx = x + dx[i];
ty = y + dy[i];
if (maze[tx][ty] == '.' && state[tx][ty] == 0)
{
state[tx][ty] = 1;
dfs(tx, ty);
state[tx][ty] = 0;
}
}
附上优化后的完整代码
int m,n;
char maze[101][101];//存放输入的迷宫
int state[101][101] = { 0 };//状态数组，令0代表未走，1代表走了
//方向数组版
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void dfs(int x, int y)
{
if (x == n && y == m)
{
printf("Yes\n");
exit(0);
}
//顺时针试探
for (int i = 0; i <=3; i++)
{
int tx, ty;
tx = x + dx[i];
ty = y + dy[i];
if (maze[tx][ty] == '.' && state[tx][ty] == 0)
{
state[tx][ty] = 1;
dfs(tx, ty);
state[tx][ty] = 0;
}
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
getchar();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%c", &maze[i][j]);
}
getchar();
}
dfs(1, 1);
printf("No\n");
return 0;
} 五.震惊！洛谷竟然不给通过
当你把以上代码信心满满地提交给洛谷，你会发现有6个测试点都超时了！！！这怎么肥事！！！
实际上，你只需把恢复现场的那行代码删掉即可AC。
state[tx][ty] = 0;
同时强调，回溯≠恢复现场
为什么呢？这需要好好讲讲。其实结合迷宫和dfs的特点我们可以想到，当dfs已经把一条路探寻完了开始回溯，其实已经意味着这条路找不到出口。如果我们还在回溯的过程中又恢复现场，那么以后程序可能还会再走一遍走这条路！一旦迷宫大起来，将是多出极大量的无用功。我们结合下面这张图感受一下。
六.将此题小小升级，找出最短路径的步数，终点改为任意
dfs一次只能探一条路，要找出最短路径，意味着要把所有通路都找出来，然后比较路径，得出最终结果。那么我们只需从如下两个方面改动以上的代码：
①修改程序退出条件，要求程序结束时把所有路都走了一遍。
去除exit(0)，改为将当前步数与上一条路径的步数比较。
②添加计数功能，并实现得出最小值的要求
我们直接多传一个计数功能的参数给dfs函数。添加一个最小值变量，每次走到终点都与上次步数相比。
不是很难，我们来看看最终代码》》》
int m,n;
int min = 999999;
char maze[101][101];//存放输入的迷宫
int state[101][101] = { 0 };//状态数组，令0代表未走，1代表走了
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void dfs(int x, int y, int count)
{
if (x == n && y == m)
{
if (count < min)
{
min = count;
}
return;
}
for (int i = 0; i <=3; i++)
{
int tx, ty;
tx = x + dx[i];
ty = y + dy[i];
if (maze[tx][ty] == '.' && state[tx][ty] == 0)
{
state[tx][ty] = 1;
dfs(tx, ty,count+1);
}
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
getchar();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%c", &maze[i][j]);
}
getchar();
}
dfs(1, 1, 0);
printf("%d\n",min);
return 0;
} acwing上没提交过，不知道能不能过，但是既然已经涉及到了最短路径，咱们最好还是用bfs写吧，下篇文章给大家带来bfs的写法~
好了，这篇文章就到这里啦，有任何问题请留言。给个点赞关注，就是对我的最大鼓励啦，谢谢~