制作迷宫地图和行走路线（3）
说在前面
前两节课中dfs()函数构造的都是不含环迷宫图案，这样任意两点之间的通道都是唯一的。如何改进程序让地图中出现环，从而增加行进路线的多样性呢？
今天我们就在上节课代码的基础上，修改dfs()函数，让程序在构造迷宫地图时，可以生成环路。内容很少，请仔细思考并认真完成课后练习哦！
第3节 使用深度优先搜索算法生成含环迷宫
要想形成环，则必须允许递归过程中可以访问某个格子超过1次；同时为了提高程序效率，不允许绘制同一通道2次；为了避免到处都是环，我们只允许程序以一定概率访问某个格子2次。
搞清楚了原理，我们就可以编写代码了。只需修改dfs()函数的部分语句即可。参考代码如下：
'''函数功能：使用深度优先搜索来生成含环迷宫，并记录通道走向函数名：dfs(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把二维数组maze和route当做全局变量，直接使用画笔绘制迷宫通道，不需要返回值。'''def dfs(r, c):maze[r][c] = 1 # 标记(r, c)来过# 走到(r, c)tt.goto(start_x+c*size, start_y-r*size)# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]# 打乱位置，下一个位置是随机的random.shuffle(d)for (i, j) in d:# 选所有可以走的下一个点，若该点未被访问过，直接访问# 若该点被访问过，但与(r,c)未连通，则以一定的几率形成环if (0<=iand 0<=jand (maze[i][j] == 0 or (i, j) not in route[r][c] and random.randint(0,63) == 0)):route[r][c].append((i, j)) # 记录与(r, c)连通的位置(i, j)route[i][j].append((r, c)) # 记录与(i, j)连通的位置(r, c)# 递归去走下一个点dfs(i, j)# 回溯到(r, c)tt.goto(start_x+c*size, start_y-r*size)
代码分析：
dfs()函数只有一处被改动了，就是判断格子是否可以访问的条件发生了变化。
在遍历格子(r,c)的相邻格子时，哪些格子是可以访问的呢？
首先当然是下标(i, j)不能越界，其次如果若该格子未被访问过，则肯定可以访问。
但如果该格子曾经被访问过呢？
那就看(i, j)和(r, c)是否曾经连通——之前有可能在处理(i, j)时，已经由它连通了(r, c)；现在轮到处理(r, c)了，就没有必要再连通这两个格子了。
即使该两个格子没有连通过，也不是非连通不可——如果所有的相邻格子都连通，那就不是随机地图了——我们允许它们有一定的概率连通，我在这里设置的概率为1/64，你也可以修改该数值。
如此这般，我们就实现了构造含环迷宫图案的功能，是不是很巧妙呢？
其他部分的代码与第2节课的一模一样，这里就不再贴出了。
课后练习
新的dfs()函数可以生成含环迷宫了，那采用深度优先搜索算法寻找路径时，只需修改一下访问相邻格子的优先级别，获得的路径就很有可能不一样。如下图所示，我们在同一个迷宫中，输入下图的起点和终点坐标，采用深度优先搜索算法寻找到了3条不同的路径（分别使用红、蓝、紫色表示）。
这张图片并不是合成的，而是重复执行了3次搜索和绘制路线的操作。主函数部分代码如下：
r1, c1 = [int(i) for i in input("起点行列下标：").split()]r2, c2 = [int(i) for i in input("终点行列下标：").split()]ws = [0.5*size, 0.3*size, 0.1*size]colors = ['red', 'blue', 'purple']for i in range(len(ws)):maze = [[0] * w for _ in range(h)] # 将maze归零，重新遍历地图maze[r1][c1] = 1ans = [(r2, c2)]dfs_ans(r1, c1)display_ans(ws[i], colors[i])
很明显，要绘制上述图案，必须修改自定义函数dfs_ans()和display_ans()中的部分代码。那么该如何修改呢？这个任务就交给聪明的你吧。
需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注Python算法，感兴趣就一起来！
相关优秀文章：