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

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])