# Python 实现的深度优先搜索实现迷宫算法
lookup_path []
history_path []
# maze [[0, 0, 1, 0, 1], [1, 0, 0, 0, 1], [0, 0, 1, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0]]
maze [[0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [1, 1, 1, 0, 0], [0, 1, 0, 0, 1], [0, 1, 0, 0, 0]]
# 打印二维数组
for k in maze:
for v in k:
print(v, end" ")
print("")
print("\n")
def up(location):
# 到达了数组顶端
if location[0] 0:
return False
else:
new_location [location[0] - 1, location[1]]
# 走过的路不再走
if new_location in history_path:
return False
# 遇到墙不走
elif maze[new_location[0]][new_location[1]] 1:
return False
else:
lookup_path.append(new_location)
history_path.append(new_location)
return True
def down(location):
# 遇到迷宫最下方的时候不能继续往下走
if location[0] len(maze) - 1: # 6行5列的二维数组行数从0开始计算所以是6-15 行
return False
else:
new_location [location[0] 1, location[1]]
# 走过的路不再走
if new_location in history_path:
return False
# 遇到墙不走
elif maze[new_location[0]][new_location[1]] 1:
return False
else:
history_path.append(new_location)
lookup_path.append(new_location)
return True
def left(location):
# 遇到迷宫最左边不能继续往左走
if location[1] 0:
return False
else:
new_location [location[0], location[1] - 1]
# 走过的路不再走
if new_location in history_path:
return False
# 遇到墙不走
elif maze[new_location[0]][new_location[1]] 1:
return False
else:
history_path.append(new_location)
lookup_path.append(new_location)
return True
def right(location):
# 遇到迷宫最右边不能继续向右移动
if location[1] len(maze[0]) - 1: # 6行5列的二维数组列数从0开始计算所以是5-14行
return False
else:
new_location [location[0], location[1] 1]
# 走过的路不再走
if new_location in history_path:
return False
# 遇到墙不走
elif maze[new_location[0]][new_location[1]] 1:
return False
else:
history_path.append(new_location)
lookup_path.append(new_location)
return True
start [0, 0]
end [5, 4]
print("start: %s --> end: %s\n" % (start, end))
lookup_path.append(start)
history_path.append(start)
while lookup_path[-1] ! end:
now lookup_path[-1]
# print("retry:%s, Lookup path:%s" % (now, route_stack))
if up(now) or down(now) or left(now) or right(now):
continue
lookup_path.pop()
print("final path: ", lookup_path)
【转自：建湖网站建设 http://www.1234xp.com/jianhu.html 复制请保留原URL】