宽度优先搜索求走出迷宫的最短长度

2020-03-08

题目描述

　　给定迷宫地图以及在迷宫中的起始位置，利用宽度优先搜索算法求解走出迷宫的最短路径长度，走出迷宫意味着达到迷宫地图的边界（所有位置下标0开始）。在迷宫地图中，０表示墙，１表示可走的路。

求解思路

　　设迷宫地图中的起点为(x,y)，并以该点为根结点，上下左右四个相连的点为后继结点，由此构建一棵4叉树，然后从根结点开始层次遍历，最先达到边界的合法路径的步长即为答案。下面是解题代码。

求解代码

  class Maze:
   def __init__(self,map,n,m,x,y):
       self.ans=0
       self.map=map
       self.n=n
       self.m=m
       self.x=x
       self.y=y

  class Solution:
   def solveMaze(self,maze): #宽度优先搜索求走出迷宫的最短长度
       maze.ans=0
       que=[(maze.x,maze.y,maze.ans)] #设置一个队列存放结点
       visit={(maze.x,maze.y):True} #visit存放该结点是否被访问过
       while len(que)>0 : #队列不为空时
           node=que[0] #出队一个结点
           del que[0]
           x=node[0]
           y=node[1]
           ans=node[2]
           if x==0 or x==n-1 or y==0 or y==n-1: #走到出口时更新数据
               if maze.ans==0 or maze.ans>ans:
                   maze.ans=ans
#满足条件的结点入队
           if x + 1 >= 0 and x + 1 < maze.n and y >= 0 and y < maze.m and (x + 1, y) not in visit and maze.map[x + 1][
               y] == 1:
               que.append((x + 1, y, ans + 1))
               visit[(x + 1, y)] = True
           if x >= 0 and x < maze.n and y + 1 >= 0 and y + 1 < maze.m and (x, y + 1) not in visit and maze.map[x][
               y + 1] == 1:
               que.append((x, y + 1, ans + 1))
               visit[(x, y + 1)] = True
           if x - 1 >= 0 and x - 1 < maze.n and y >= 0 and y < maze.m and (x - 1, y) not in visit and maze.map[x - 1][
               y] == 1:
               que.append((x - 1, y, ans + 1))
               visit[(x - 1, y)] = True
           if x >= 0 and x < maze.n and y - 1 >= 0 and y - 1 < maze.m and (x, y - 1) not in visit and maze.map[x][
               y - 1] == 1:
               que.append((x, y - 1, ans + 1))
               visit[(x, y - 1)] = True

       return maze.ans #返回最终求解的最短长度

  if __name__ == '__main__':

   raw = input().split('\n')[0].strip().split(' ')
   n = int(raw[0])
   m = int(raw[1])

   map = [[int(raw) for raw in input().split('\n')[0].strip().split(' ')] for i in range(n)]

   raw = input().split('\n')[0].strip().split(' ')
   x = int(raw[0])
   y = int(raw[1])

   maze = Maze(map, n, m, x, y)
   sol = Solution()
   print (sol.solveMaze(maze))