lingzixi
2022-06-30 20:12
采纳率: 100%
浏览 23

python走迷宫深度优先搜索

有哦人知道这个程序要怎么改成打印出来的迷宫路径使用星号表示的吗,就是矩阵里面能显示路径

img


```python
from numpy import *
def findpath(puzzle, start, end):
    # 四个方向
    d = [(-1,0),(0,1),(1,0),(0,-1)]
    vis = [[-1 for _ in range(len(puzzle[0]))] for _ in range(len(puzzle))]
    #迷宫矩阵,0表示路, 1表示墙 
    vis[start[0]][start[1]]=start
    dfs = [start]     
    while dfs:
        x,y = dfs.pop()    #取栈顶及其探查方向
        for i in range(4): #依次检查未探查方向
            m = x+d[i][0]
            n = y+d[i][1]  #算出下一位
            puzzle[start[0]][start[1]] = 6 #把走过的记录为6
            if 0<=m<len(puzzle) and 0<=n<len(puzzle[0]) and puzzle[m][n]==0 and vis[m][n]==-1:   #遇到未探查的新位置 
                dfs.append((x,y))    #原位置和下一方向入栈
                dfs.append((m,n))
                vis[m][n]=(x,y)      #新位置入栈
                puzzle[start[0]][start[1]] = 6 #把走过的记录为6
                if end==(m,n): #到达出口,打印路径
                    return dfs
                break   #退出内层循环,下次迭代将以新栈顶为当前位置继续
    return dfs  #找不到路径
    
puzzle = zeros((10, 10), dtype=float) # 先创建一个全零方阵puzzle;,并且数据的类型设置为float浮点型
f = open('test2.txt') # 打开数据文件文件
lines = f.readlines() # 把全部数据文件读到一个列表lines中
puzzle_row = 0  # 表示矩阵的行,从0行开始
for line in lines: # 把lines中的数据逐行读取出
         list = line.strip('\n').split(' ') # 处理逐行数据:strip表示把头尾的'\n'去掉,split表示以空格来分割行数据,然后把处理后的行数据返回到list列表中
         puzzle[puzzle_row:] = list[0:10] # 把处理后的数据放到方阵A中。list[0:4]表示列表的0,1,2,3列数据放到矩阵A中的A_row行
         puzzle_row += 1 # 然后方阵A的下一行接着读
print(puzzle)        
start = eval(input("请输入起始坐标(x,y):"))
end = eval(input("请输入终点坐标(m,n):"))
res = findpath(puzzle, start, end)
if res:print(res)
else: print('无路可走')


```

2条回答 默认 最新

相关推荐 更多相似问题