经典数据结构解决迷宫问题（Python实现）

首先自定义一个二维数组

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

0：表示路

1：表示墙体

一.深度优先搜索+回溯（使用栈来存储已走过的路径）

1,定义四个lambda表达式作为右左下上四个方向。

2.从初始结点开始，当下一个结点可以走的时候，自己的坐标点入栈。并标记为已经走过。

3.当没有下一个结点可以走的时候，出栈，说明此路不通。回溯到可以有下一个结点可以走的结点处。重新开始步骤2.

4.当找到目标结点的时候，遍历栈中的元素，即为一条可以走通的路。不一定是最优的路线规划。

#使用栈来存储路径 maze = [     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],     [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],     [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],     [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],     [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],     [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],     [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] dirs = [     lambda x, y: (x + 1, y),     lambda x, y: (x - 1, y),     lambda x, y: (x, y - 1),     lambda x, y: (x, y + 1) ]  def maze_path(x1,y1,x2,y2):     stack = []     stack.append((x1,y1))     while len(stack)>0:         curNode = stack[-1]  #当前的节点         if curNode[0] == x2 and curNode[1] == y2:             for p in stack:                 print(p)             return True          for di in dirs:             nextNode = di(curNode[0],curNode[1])  #如果下一个结点可以走             if maze[nextNode[0]][nextNode[1]] ==0:                 stack.append(nextNode)                 maze[nextNode[0]][nextNode[1]] = 2  #标记为已经走过                 break         else:             maze[nextNode[0]][nextNode[1]] = 2             stack.pop()     else:         print("没有路")         return False  maze_path(1,1,8,8)

二.广度优先算法（使用队列来储存已经走过的路线）

1.定义四个lambda表达式作为右左下上四个方向。

2..从初始结点开始，如果有一个节点可以走的时候，自己的坐标点+自己的上一个结点入队列，并表示为已经走过。

3.只要队列中铀元素就把步骤2的队列中的元素出队列存放在数组path中。

4.当找到目标结点的时候，结束查找。如果找不到目标结点，即没有一条路可以到达。

5.通过path数组中第三项元素指向的位置，逆序打印path中前两项元素，即为最后的路线。一定时最优的路线。

from collections import deque #使用队列 maze = [     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],     [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],     [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],     [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],     [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],     [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],     [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] dirs = [     lambda x, y: (x + 1, y),     lambda x, y: (x - 1, y),     lambda x, y: (x, y - 1),     lambda x, y: (x, y + 1) ]   def print_r(path):     curNode = path[-1]     print(curNode)      realpath=[]      while curNode[2] != -1:         realpath.append(curNode[0:2])         curNode = path[curNode[2]]      realpath.append(curNode[0:2])  # 起点     realpath.reverse()     for node in realpath:         print(node)   def maze_path_queue(x1, y1, x2, y2):     queue = deque()     queue.append((x1, y1, -1))   #起点     path = []     while len(queue) > 0:    #只要队不为空         curNode = queue.pop()   #队首出队         path.append(curNode)         if curNode[0] == x2 and curNode[1] == y2:             print_r(path)             return True         for dir in dirs:             nextNode = dir(curNode[0], curNode[1])      #下一个节点             if maze[nextNode[0]][nextNode[1]] == 0:                 queue.append((nextNode[0], nextNode[1], len(path) - 1))  # 后续节点进队，记录哪个结点带她来的                 maze[nextNode[0]][nextNode[1]] = 2  # 标记已经走过     else:         print("没有路")         return False maze_path_queue(1,1,8,8)