bfs迷宫问题最短路径

BFS迷宫问题最短路径算法：

1. 创建一个队列，将起点入队。
2. 创建一个dist数组，用于记录每个位置到起点的最短距离，初始化为无穷大。
3. 将起点的dist值设为0。
4. 不断从队列中取出一个位置，遍历该位置的四个方向（上、下、左、右），如果该方向的位置可以走且未访问过，则将该位置入队，并将其dist值设为当前位置的dist值+1。
5. 重复步骤4，直到队列为空或者到达终点。
6. 若到达终点，则返回终点的dist值作为最短路径长度，否则表示无法到达终点。

代码实现：

def bfs(maze, start, end):
    queue = [start]
    n = len(maze)
    m = len(maze[0])
    dist = [[float('inf')] * m for _ in range(n)]
    dist[start[0]][start[1]] = 0
    while queue:
        x, y = queue.pop(0)
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 0 and dist[nx][ny] == float('inf'):
                queue.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1
                if (nx, ny) == end:
                    return dist[nx][ny]
    return -1  # 无法到达终点

其中，maze是一个二维数组，0表示可以走，1表示障碍物；start和end是起点和终点的坐标。