# 使用 Python 实现的广度优先搜索实现迷宫算法
class Maze(object): def __init__(self, maze, start, end): self.maze = maze self.start = start self.end = end self.direction = [[-1, 0], [0, -1], [1, 0], [0, 1]] # 移动方向顺序: 上左下右 def move(self, x, y): """ 执行迷宫的上下左右操作 :param x: 起始坐标 :param y: 移动的方向 :return: 新的坐标 """ return [x[0] + y[0], x[1] + y[1]] def at(self, grid, x): """ 传入一个maze和坐标，判断坐标是否越界，如果没有越界根据坐标返回对应maze中的数值 :param grid: maze :param x: 查找坐标 :return: maze中的数值和状态 """ # 判断row 是否越界 if x[0] < 0 or x[0] >= len(grid): return 0, False # 判断col 是否越界 if x[1] < 0 or x[1] >= len(grid[0]): return 0, False return grid[x[0]][x[1]], True def walk(self): """ 创建一个新的二维数组，self.maze每走一步，就在这个新的二维数组对应位置上记录行走的步数 :return: 记录了行走步数的二维数组 """ # 创建一个大小和self.maze一样大小的二维数组，此二维数组中所有的值初始化为0，用来记录行走的步数 steps = [[i * 0 for i in range(len(self.maze[0]))] for j in range(len(self.maze))] Q = [self.start] while len(Q) > 0: index = Q[0] # 找到出口 if index == self.end: break Q = Q[1:] for d in self.direction: next = self.move(index, d) val, ok = self.at(self.maze, next) # 越界或者撞墙，跳过 if not ok or val == 1: continue # 新的二维数组中移动的下一个点如果值不是0的话，说明已经走过这个点，直接跳过 val, ok = self.at(steps, next) if not ok or val != 0: continue # 回到原点 if next == self.start: continue # 将steps中每走一步，记录当前的步数 val, ok = self.at(steps, index) if ok: steps[next[0]][next[1]] = val + 1 # 每走一步，将此时的位置加入到队列中 Q.append(next) return steps def path(self, grid): """ 根据steps计算最优路径 :param grid: steps迷宫图 :return: 存放路径的列表 """ last = grid[len(maze) - 1][len(maze[0]) - 1] lookup_path = [[len(maze) - 1, len(maze[0]) - 1], ] while last > 0: last -= 1 index = lookup_path[-1] for d in self.direction: next = self.move(index, d) val, err = self.at(grid, next) if val == last: lookup_path.append(next) break return lookup_pathif __name__ == '__main__': # maze = [[0, 0, 1, 0, 1], [1, 0, 0, 0, 1], [0, 0, 1, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0]] maze = [[0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [1, 1, 1, 0, 0], [0, 1, 0, 0, 1], [0, 1, 0, 0, 0]] # 打印二维数组 print("原始迷宫图:") for k in maze: for v in k: print("%2d" % v, end=" ") print("") print("\n") print("行走路线图:") step = Maze(maze, [0, 0], [len(maze) - 1, len(maze[0]) - 1]) steps = step.walk() for k in steps: for v in k: print("%2d" % v, end=" ") print("") print("\n") print("走出迷宫共需要%s步\n" % steps[len(maze) - 1][len(maze[0]) - 1]) # 计算最优路径 path = step.path(steps) path.reverse() print("最优路径是: ", path)