制作迷宮地圖和行走路線（2）

'''函數(shù)功能：使用深度優(yōu)先搜索來(lái)生成不含環(huán)迷宮，并記錄通道走向函數(shù)名：dfs(r, c)參數(shù)表：r,c -- 表示當(dāng)前格子在二維數(shù)組maze中的行列下標(biāo)。返回值：把二維數(shù)組maze和route當(dāng)做全局變量，直接使用畫筆繪制迷宮通道，不需要返回值。''' def dfs(r, c):    # 標(biāo)記(r, c)來(lái)過(guò)    maze[r][c] = 1    # 走到(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)]    # 打亂位置，下一個(gè)位置是隨機(jī)的    random.shuffle(d)    for (i, j) in d:        # 選所有可以走的下一個(gè)點(diǎn)，如果此點(diǎn)在范圍內(nèi)并且沒(méi)去過(guò)        if 0<=iand 0<=jand maze[i][j]==0:            route[r][c].append((i, j)) # 記錄與(r, c)連通的位置(i, j)            route[i][j].append((r, c)) # 記錄與(i, j)連通的位置(r, c)            # 遞歸去走下一個(gè)點(diǎn)            dfs(i, j)            # 回溯到(r, c)            tt.goto(start_x+c*size, start_y-r*size)

'''函數(shù)功能：使用深度優(yōu)先搜索來(lái)尋找路徑函數(shù)名：dfs_ans(r, c)參數(shù)表：r,c -- 表示當(dāng)前格子在二維數(shù)組maze中的行列下標(biāo)。返回值：把列表maze和ans當(dāng)做全局變量，若從當(dāng)前格子出發(fā)能夠到達(dá)終點(diǎn)，返回True，否則False。''' def dfs_ans(r, c):    if r==r2 and c==c2:        return True    for (i, j) in route[r][c]:        if maze[i][j] == 0: # 如果沒(méi)有去過(guò)該點(diǎn)，則遞歸搜索該點(diǎn)            maze[i][j] = 1  # 標(biāo)記該點(diǎn)已經(jīng)來(lái)過(guò)            # 遞歸去走下一個(gè)點(diǎn)            if dfs_ans(i, j): #若當(dāng)前格子與終點(diǎn)連通，將當(dāng)前格子行列下標(biāo)加入到ans                ans.append((r, c))                return True    return False

'''函數(shù)功能：根據(jù)ans的值，繪制使用深度優(yōu)先搜索獲得的路徑函數(shù)名：display_ans()參數(shù)表：直接使用列表ans的元素值，不需要任何參數(shù)。返回值：直接利用畫筆繪制路線，不需要返回值。''' def display_ans():    tt.speed(1)    tt.pensize(size*0.5) # 路線粗細(xì)    tt.color("red")    tt.penup()    tt.goto(start_x+ans[-1][1]*size, start_y-ans[-1][0]*size)    tt.pendown()    for (r, c) in ans[-2::-1]: #逆序遍歷ans，剛好可以順序輸出從起點(diǎn)到終點(diǎn)的路線        tt.goto(start_x+c*size, start_y-r*size)

tt.TurtleScreen._RUNNING = True  # 啟動(dòng)繪圖，在IDE中運(yùn)行加這句可避免報(bào)錯(cuò)tt.ht()#隱藏筆頭tt.bgcolor('black')tt.color("white") # 路線顏色tt.speed(3)w, h = 20, 20 # 迷宮寬和高size = 30 # 每格大小tt.pensize(size*0.8) # 路線粗細(xì)maze = [[0] * w for i in range(h)]route = [[[] for j in range(w)] for i in range(h)] #記錄迷宮路線
start_x = -w / 2 * sizestart_y = h / 2 * size# 讓畫筆到左上角位置tt.penup()tt.goto(start_x, start_y)tt.pendown()# 從左上角(0, 0)開(kāi)始走dfs(0, 0) # 使用深度優(yōu)先搜索來(lái)生成不含環(huán)迷宮
# 使用深度優(yōu)先搜索來(lái)尋找路徑r1, c1 = [int(i) for i in input("起點(diǎn)行列下標(biāo)：").split()]r2, c2 = [int(i) for i in input("終點(diǎn)行列下標(biāo)：").split()]maze = [[0] * w for _ in range(h)] # 將maze歸零，重新遍歷地圖maze[r1][c1] = 1  # 標(biāo)記起點(diǎn)已經(jīng)去過(guò)了ans = [(r2, c2)]  # 先將終點(diǎn)加入到ans中，之后逆序添加各個(gè)格子dfs_ans(r1, c1)   # 使用深度優(yōu)先搜索來(lái)尋找路徑display_ans()     # 繪制使用深度優(yōu)先搜索獲得的路徑
tt.done()  # 結(jié)束繪圖，這將不會(huì)關(guān)閉窗口