python走迷宫_Python

Python走迷宫问题可以使用深度优先搜索（DFS）算法来解决，在这个问题中，我们需要找到一条从起点到终点的路径，我们可以使用递归来实现DFS算法。

我们需要定义一个二维数组来表示迷宫，其中0表示墙，1表示可以走的路，2表示已经走过的路，3表示起点，4表示终点，我们还需要一个二维数组来记录每个位置的上一个位置，以便我们可以找到从终点到起点的路径。

接下来，我们需要实现DFS算法，我们从起点开始，每次尝试上下左右四个方向，如果某个方向是路并且没有被走过，我们就继续递归搜索，如果找到了终点，我们就返回True，如果四个方向都走不通，我们就回溯到上一个位置。

我们需要实现一个函数来打印出从起点到终点的路径。

下面是完整的代码：

def dfs(maze, x, y, pre):
    if maze[x][y] == 4:
        return True
    for dx, dy in [(1, 0), (1, 0), (0, 1), (0, 1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] == 1 and pre[nx][ny] == 0:
            pre[nx][ny] = 1
            maze[nx][ny] = 2
            if dfs(maze, nx, ny, pre):
                return True
            pre[nx][ny] = 0
            maze[nx][ny] = 1
    return False
def print_path(pre, x, y):
    if pre[x][y] == 0:
        return
    print((x, y))
    print_path(pre, x // 2, y // 2)
def solve_maze(maze):
    pre = [[0] * len(maze[0]) for _ in range(len(maze))]
    start_x, start_y = None, None
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] == 3:
                start_x, start_y = i, j
                break
        if start_x is not None:
            break
    if dfs(maze, start_x, start_y, pre):
        print_path(pre, start_x, start_y)
    else:
        print("No solution.")
maze = [
    [3, 1, 1, 1, 1],
    [1, 1, 1, 0, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 0, 0, 1],
    [1, 1, 1, 1, 4]
]
solve_maze(maze)

在这个例子中，我们有一个5×5的迷宫，起点在左上角，终点在右下角，运行上面的代码，我们可以看到从起点到终点的路径被打印出来。

FAQs

Q1: 如果迷宫有多个解，这个算法能找到所有的解吗？

A1: 这个算法只能找到一个解，因为它在找到第一个解后就停止了，要找到所有的解，我们需要修改算法，使其在找到一个解后继续搜索其他路径。

Q2: 这个算法的时间复杂度是多少？

A2: 这个算法的时间复杂度是O(n^2)，其中n是迷宫的大小，因为我们需要遍历整个迷宫来找到一条路径。