迷宫问题一直是计算机基础算法中经典的问题之一。对于最短路径问题,我们可以使用 Python 中的广度优先搜索算法来解决迷宫最短路径的问题。
from collections import deque def bfs(maze, start, end): queue = deque([start]) visited = set() directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: x, y, dist = queue.popleft() if (x, y) == end: return dist if (x, y) in visited: continue visited.add((x, y)) for dx, dy in directions: new_x, new_y = x + dx, y + dy if 0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]): if (new_x, new_y) not in visited and maze[new_x][new_y] != '#': queue.append((new_x, new_y, dist + 1)) return -1
上面的代码表示通过广度优先搜索从起点开始,不断向四个方向进行扩展,直到到达终点,找到最短路径。我们通过一个队列存储需要扩展的点,并使用一个 visited 集合来记录已经访问过的点。循环扩展到终点时,返回最短距离。
我们可以使用一个二维数组来表示迷宫,其中 . 表示可走的路,# 表示墙壁阻挡,S 表示起点,E 表示终点。
maze = [ ['#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '.', '.', '.', '#', '.', '.', '.', '#'], ['#', '.', '#', '.', '#', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '.', '.', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#'] ] start = (1, 1, 0) # 起始点和初始距离 end = (3, 6) # 终点 dist = bfs(maze, start, end) print("Distance:", dist)
实现了上述算法,我们便可成功地找出迷宫中的最短路径。