如何用Python编程实现迷宫探索算法？

Python走迷宫

问题描述

编写一个Python程序，实现一个自动走迷宫的功能，迷宫由二维数组表示，其中0表示可以通过的路径，1表示墙壁或障碍物，2表示起点，3表示终点。

解决方案

我们可以使用深度优先搜索（DFS）算法来解决这个问题，以下是一个简单的实现：

def dfs(maze, x, y, path):
    if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or maze[x][y] == 1:
        return False
    if maze[x][y] == 3:
        path.append((x, y))
        return True
    maze[x][y] = 1  # Mark the cell as visited
    path.append((x, y))
    
    # Check all four directions (up, down, left, right)
    if dfs(maze, x 1, y, path) or dfs(maze, x + 1, y, path) or dfs(maze, x, y 1, path) or dfs(maze, x, y + 1, path):
        return True
    
    path.pop()  # Backtrack if no path found
    return False
def find_path(maze):
    start_x, start_y = None, None
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] == 2:
                start_x, start_y = i, j
                break
        if start_x is not None:
            break
    
    if start_x is None:
        return []
    
    path = []
    dfs(maze, start_x, start_y, path)
    return path
Example usage:
maze = [
    [2, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 1],
    [1, 1, 1, 3]
]
print(find_path(maze))

在这个例子中，dfs函数是递归地搜索迷宫的每个可能的方向，当找到终点时，它将返回True并将路径添加到path列表中，如果没有找到路径，它将回溯并尝试其他方向。find_path函数首先找到起点的位置，然后调用dfs函数开始搜索，它返回找到的路径。