迷宫问题 宽度优先搜索

迷宫问题指的是在一个由障碍物和空地组成的矩阵中，从起点到终点的最短路径问题。其中，障碍物表示不可通过的区域，空地表示可以通过的区域。宽度优先搜索是一种基于图的遍历算法，可以用来解决迷宫问题。以下是宽度优先搜索解决迷宫问题的步骤：

1. 定义队列，并将起点加入队列。
2. 定义一个二维数组visited，用于记录每个位置是否已被访问过。将起点标记为已访问。
3. 进入循环，只要队列不为空，就继续搜索：
a. 从队列中取出一个位置。
b. 如果该位置是终点，返回路径长度。
c. 否则，遍历该位置的上下左右四个方向，如果该方向是空地且未被访问过，则将该位置加入队列，并标记为已访问。
4. 如果循环结束时仍未找到终点，则说明不存在从起点到终点的路径。

以下是一个Python实现的宽度优先搜索迷宫问题的代码示例：

from collections import deque

def bfs(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    queue = deque([(start[0], start[1], 0)])
    visited = [[False] * cols for _ in range(rows)]
    visited[start[0]][start[1]] = True
    
    while queue:
        x, y, steps = queue.popleft()
        if (x, y) == end:
            return steps
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and not visited[nx][ny]:
                queue.append((nx, ny, steps + 1))
                visited[nx][ny] = True
                
    return -1  # 无解情况

# 示例
maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [0, 1, 0, 0],
    [0, 0, 1, 0]
]
start = (0, 0)
end = (3, 3)
print(bfs(maze, start, end))  # 输出 6

在上述代码中，maze表示迷宫，其中0表示空地，1表示障碍物；start和end分别表示起点和终点。函数bfs使用宽度优先搜索算法来计算从起点到终点的最短路径长度。其中，visited数组用于记录每个位置是否已被访问过，steps表示当前位置到起点的路径长度。最后返回的是起点到终点的最短路径长度。如果不存在从起点到终点的路径，则返回-1。