如果你没有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的写法~

好了，这篇文章就到这里啦，有任何问题请留言。给个点赞关注，就是对我的最大鼓励啦，谢谢~