python 迷宫问题 bfs

广度优先搜索（BFS）算法可以用来解决迷宫问题。在给定的迷宫中，起点和终点已知，障碍物和空地也已知。BFS算法可以找到从起点到终点的最短路径。下面是解决迷宫问题的Python代码，其中使用了BFS算法：

from collections import deque

n, m = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
vis = [[0 for i in range(m)] for j in range(n)]

x1, y1 , x2, y2 = map(int,input().split())

q = deque()

def bfs(x,y):
    q.append([x,y])
    vis[x][y] =1
    while q:
        now = q.popleft()
        nx = now[0]
        ny = now[1]
        if nx == x2-1 and ny == y2-1:
            break
        for i in d:
            dx = nx+i[0]
            dy = ny+i[1]
            if 0 <= dx < n and 0 <= dy < m:
                if vis[dx][dy] == 0 and g[dx][dy] == 1:
                    q.append([dx,dy])
                    vis[dx][dy] = vis[nx][ny] + 1
    return vis[x2-1][y2-1] - 1

print(bfs(x1-1,y1-1))

在这个代码中，我们首先输入了迷宫的大小和迷宫的地图。然后，我们定义了一个方向列表d，它包含了四个方向。接下来，我们定义了一个vis列表，用于记录每个位置是否被访问过。然后，我们输入了起点和终点的坐标，并定义了一个队列q。最后，我们定义了一个bfs函数，它使用BFS算法来搜索从起点到终点的最短路径，并返回路径长度。在主函数中，我们调用bfs函数并输出结果。