说在前面

前4节课我们都是直接绘制随机迷宫图案，没有存储迷宫中各坐标点是通道还是墙壁的信息，这与通常的迷宫地图不一样。本节课我们使用传统的方法来绘制迷宫地图，即利用二维数组存储迷宫各坐标点信息，再根据二维数组绘制迷宫地图。

程序先生成随机二维数组，然后手动修改坐标点信息，以便绘制想要的地图。有了二维数组之后，就可以采用深度优先搜索算法来绘制地图了。地图绘制好了后，可以输入起点和终点坐标，根据深度优先搜索或者广度优先搜索算法寻找行走路线，其中使用广度优先搜索算法获得的是最短路径。

第5节使用深度优先搜索算法绘制二维迷宫

我们在主函数中定义二维数组maze来表示地图，maze的元素值只有两种情况，1表示通道，0表示墙壁。先为maze随机赋值，输出其值后，复制粘贴回代码中，可以直观地看到各元素值，再手动修改坐标点信息，以便绘制想要的地图。

除了存储地图信息的二维数组maze，我们还定义了一个二维数组book，用来标记某个位置是否已经去过，以免重复访问同一位置。

参考代码如下：

w, h = 20, 20 # 迷宫宽和高# 迷宫数据列表，1表示通道，0表示墙壁maze = [[random.randint(0,1) for j in range(w)] for i in range(h)]for i in range(h):print(maze[i])maze = [[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],[1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1],[1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1],[1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1],[0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1],[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0],[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0],[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1],[0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0],[0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0],[1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1],[1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1],[1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0],[1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0],[1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],[0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1],[0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1],[0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0],[1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]book = [[0] * w for i in range(h)] #标记该位置是否已经去过

2.使用深度优先搜索算法绘制迷宫地图：

根据maze存储的地图信息，我们可以调用函数dfs()，采用深度优先搜索算法来绘制迷宫地图。因为地图中所有通道不一定都是连通的，也就是说一次深搜不一定能把所有的通道都绘制出来，所以需要遍历每一个位置，每遇到未被访问过的通道，都要调用函数dfs()。直到把所有的通道都绘制出来。

主函数中调用函数的代码如下：

for i in range(h):for j in range(w):if maze[i][j] == 1 and book[i][j] == 0:tt.penup()dfs(i, j) # 使用深度优先搜索来生成迷宫

自定义函数dfs()有两个参数r和c，分别表示当前格子在二维数组maze中的行、列下标。若当前位置(r, c)为未访问过的通道，则调用函数draw_rectangle()在该处绘制白色矩形。接下来遍历(r, c)的周围位置，若能走通，则递归去绘制下一个点，否则回溯到上一个位置。

自定义函数及函数头说明如下：

"""函数功能：以(x, y)作为左上角坐标，绘制宽、高分别为w、h的矩形，并填充颜色c函数名：draw_rectangle(x, y, w, h)参数表：x,y -- 表示矩形在屏幕中的左上角坐标；w,h -- 表示矩形的宽和高；c -- 表示矩形的填充颜色。返回值：直接使用画笔绘制并填充矩形，不需要返回值。""" def draw_rectangle(x, y, w, h, c):tt.penup()tt.goto(x, y)tt.pendown()tt.color(c)tt.begin_fill()for i in range(2):tt.forward(w)tt.right(90)tt.forward(h)tt.right(90)tt.end_fill()"""函数功能：使用深度优先搜索来生成迷宫 函数名：dfs(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把二维数组book当做全局变量，直接使用画笔绘制迷宫通道，不需要返回值。""" def dfs(r, c):# 标记(r, c)来过book[r][c]= 1# 绘制(r, c)draw_rectangle(start_x+c*size-size//2, start_y-r*size+size//2, size, size, "white")# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:# 选所有可以走的下一个点，如果此点在范围内并且没去过if 0<=i
3.使用深度优先搜索寻找并绘制路径：
绘制好迷宫地图以后，就可以输入起点和终点坐标，寻找连接二者的路径了。因为在绘制地图过程中，二维数组book的值发生了变化，所以需要先将book归零，以便重新遍历地图。
我们从起点(r1, c1)开始，调用函数dfs_ans()，使用深度优先搜索算法来寻找路径。设置全局变量ans用来逆序存储路线上的各个格子的行列下标。待找到从起点到终点的路径以后，再调用函数display_ans()绘制路径。
主函数中调用函数的代码如下：
# 使用深度优先搜索来寻找路径tt.delay(1)r1, c1 = [int(i) for i in input("起点行列下标：").split()]r2, c2 = [int(i) for i in input("终点行列下标：").split()]book = [[0] * w for i in range(h)] # 将book归零，重新遍历地图book[r1][c1] = 1 # 标记起点已经去过了ans = []         # 用来逆序存储路线上的各个格子的行列下标dfs_ans(r1, c1)  # 使用深度优先搜索来寻找路径ans.append((r1, c1)) # 将起点添加到ans中display_ans()     # 绘制使用深度优先搜索获得的路径tt.done()#结束绘图，这将不会关闭窗口
自定义函数dfs_ans()与函数dfs()的结构相似，都是两个参数r和c，用来表示当前格子在二维数组maze中的行、列下标。若当前位置(r, c)恰好为终点，则直接返回True；否则遍历其周围的格子，递归处理下一个可通行的位置。若当前格子与终点连通，将当前格子行列下标加入到ans，并返回True。
程序有一个有趣的地方，就是随机打乱数组d的元素顺序，这样遍历d时，下一个位置是随机的，从而导致每次运行程序时可以得到不同的搜索路线。
自定义函数display_ans()根据ans的值，绘制使用深度优先搜索获得的路径。因为列表ans是按照从终点到起点的顺序存储位置坐标的，故在绘制路径时，需要逆序遍历ans，才能绘制从起点到终点的路径。
自定义函数及函数头说明如下：
"""函数功能：使用深度优先搜索来寻找路径函数名：dfs_ans(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把列表book和ans当做全局变量，若从当前格子能够到达终点，返回True，否则False。""" def dfs_ans(r, c):if r==r2 and c==c2:return True# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]# 打乱位置，下一个位置是随机的，这样每次的搜索路线可能不一样random.shuffle(d)for (i, j) in d:if 0<=i
课后练习
本文展示的成品效果图中，有红、绿两种颜色的路径，其中红色为采用深度优先搜索算法获得的路径，绿色路径较短，它是采用广度优先搜索算法获得的最短路径。
现在请你在原有代码的基础上，增加程序功能，自定义相关函数，使用广度优先搜索算法寻找路径，并用绿色画笔把路径绘制出来。
需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注Python算法，感兴趣就一起来！
相关优秀文章：
阅读代码和写更好的代码
最有效的学习方式
Python算法之旅文章分类