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