问题描述
下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR的顺序通过迷宫，一共10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫(30行50列)，请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D<L<R<U。
解决方案
构建位置信息，可以把01位置坐标化，同时建立围墙然后通过广度优先搜索法来找路径，再把路径转换成UDLRf方位信息。（图示结构及相关理解如下两张图）
import collections
#导入collections库，会运用deque模块（队列）
f=open(”maze.txt”,”r”)
#打开文件，这里的maze.txt为题目中的30行50列的迷宫的文件
s=f.readlines()
# 读取文件的所有行，形成一个列表，每一行为一个元素
# ---------------------------------------------------------
position = {}
'''
建立坐标位置对应0/1的字典
先建围墙的坐标，由于1代表障碍，所以围墙设为1
'''
height=s.__len__()
width=s[0].__len__()
print(height,width)
for y_wall in range(0,height):
position[(0, y_wall)]='1'
position[(width, y_wall)]='1'
for x_wall in range(0, height):
position[(x_wall,0)]='1'
position[(x_wall,s[0].__len__())]='1'
y=1
#y位置的初始值
for y_position in s:
# 遍历s中的每一行
for xy_index in range(len(y_position)-1):
# xy_index:0,1,2...49
position[(xy_index + 1, y)]=y_position[xy_index]
# 读取每一个0/1位置的坐标，将其加入到字典中去
y=y+1
# 每读取一行之后，下一行y位置的值加1
# 上面程序运行之后，01文件的每个点的坐标建立完毕，存储在字典position中
# ---------------------------------------------------------
# 下面开始对每个点开始搜索并且开始记录
print(position)
m_deque=collections.deque()
# 创建队列
start=(1,1)
end=(width-1, height-1)
checked_position=[]
# 记录检查过的点的坐标信息的一个列表
m_deque.append(start)
# 把起点加入到搜索队列中
while m_deque:
# 只要队列不空，就继续搜索
to_check_position=m_deque.popleft()
# 把队列的第一个位置拿出来检查
if to_check_position not in checked_position:
# 如果这个点（坐标）没有被检查过
if to_check_position==end:
print("ok!")
break
# 如果这个点为出口的点的坐标，那么输出ok，同时循环结束
else:
#否则循环继续
checked_position.append(to_check_position)
# 记录已经检查过的坐标
up_position=(to_check_position[0],to_check_position[1]-1)
down_position=(to_check_position[0],to_check_position[1]+ 1)
left_position=(to_check_position[0]-1
,to_check_position[1])
right_position=(to_check_position[0]+1, to_check_position[1])
# 返回正在被检查的坐标的上下左右点位置的坐标
# 不能用elif，只能每个都是if
if position.get(up_position)=="0"and up_position not in checked_position:
m_deque.append(up_position)
# 如果这个上面的点的坐标代表的是0，而且这个点坐标不在被检查过的列表里面，那么就把这个点的坐标位置加入到队列当中，下面同理
if position.get(down_position)=="0" and down_position not in checked_position:
m_deque.append(down_position)
if position.get(left_position)=="0" and left_position not in checked_position:
m_deque.append(left_position)
if position.get(right_position)=="0"and right_position not in checked_position:
m_deque.append(right_position)
all_line=checked_position+[end]
# 这个all_line表示记录过的点，再加上出口这个点（就是说我这个程序从起点到终点它到过了什么地方，那么接下来就会通过这个列表找出迷宫的路）
#--------------------------------------------------------
# 寻找出那条从起点到终点的路径every_end=(end)
# 寻找从终点开始，往前找
line=[]
# 路径坐标的列表
line_dulr=[]
# 路径上下左右方向的列表
while every_end!=start:
# 只要找到的这个点不是起点，那么就继续找
up_xy=(every_end[0],every_end[1]-1)
down_xy=(every_end[0],every_end[1]+1)
left_xy=(every_end[0]-1,every_end[1])
right_xy=(every_end[0]+1,every_end[1])
# 返回这个被找的点的上下左右的坐标信息
# 注意这个下面必须要用elif,不能用都用if
if position.get(up_xy)=="0"and up_xy in all_line:
# 如果这个点的上面点是0（表示可以走的路），而且这个点是被记录过的（表示这个点就是路径中的一个点）
index=all_line.index(up_xy)
# 返回这个点在列表中的位置
all_line=all_line[:index]
# 更新这个列表，就是说这个列表的最后一个元素是该点，那么下次再往前找位置的时候，眼光想起看就行了
line.append(up_xy)
# 既然这个点是的话，那么就把这个点添加到最终的路径里面去
line_dulr.append("D")
# 由于是反向走的，所以上面的这个坐标就要往下走
every_end=up_xy
# 更新这个节点，然后从这个节点开始继续向前走
elif position.get(down_xy)=="0"and down_xy in all_line:
index=all_line.index(down_xy)
all_line=all_line[:index]
line.append(down_xy)
every_end=down_xy
line_dulr.append("U")
elif position.get(left_xy)=="0"and left_xy in all_line:
index=all_line.index(left_xy)
all_line=all_line[:index]
line.append(left_xy)
every_end=left_xy
line_dulr.append("R")
elif position.get(right_xy)=="0"and right_xy in all_line:
index=all_line.index(right_xy)
all_line=all_line[:index]
line.append(right_xy)
every_end=right_xy
line_dulr.append("L")
# print(line)
# 路线的坐标
# print(line_dulr)line_s=""
for i in line_dulr:
line_s=line_s+i
# 把列表中的每个元素全都连接起来
print(line_s[::-1])
结语
本章大致写了用队列的方法来解答这个迷宫的问题，以一个点为突破口，遍历所有可能并记录可行的方法，再进行所有可行方法的字典序的对比，打印出最佳方案。虽然这种方法可行，但是运算大，代码也比较复杂，我在想，是否可以用递归的方法来做，却暂时没有合适的思路，希望各位读者能够为我解答。
主编：欧洋
作者：陈鱼江、冯睿、肖华
