算法创作|迷宫问题解决方案

问题描述下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。010000000100001001110000迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按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...49position[(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，只能每个都是ifif  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,不能用都用ifif 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_xyline_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_xyline_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_xyline_dulr.append("L")# print(line)# 路线的坐标# print(line_dulr)line_s=""for i in line_dulr:line_s=line_s+i# 把列表中的每个元素全都连接起来print(line_s[::-1])结语本章大致写了用队列的方法来解答这个迷宫的问题，以一个点为突破口，遍历所有可能并记录可行的方法，再进行所有可行方法的字典序的对比，打印出最佳方案。虽然这种方法可行，但是运算大，代码也比较复杂，我在想，是否可以用递归的方法来做，却暂时没有合适的思路，希望各位读者能够为我解答。主编：欧洋作者：陈鱼江、冯睿、肖华