python 迷宫宽度优先

Python迷宫宽度优先搜索算法是一种用于解决迷宫问题的算法。该算法通过从起点开始，逐步向外扩展搜索，直到找到终点为止。在搜索过程中，算法会记录已经访问过的节点，以避免重复访问。与深度优先搜索算法不同的是，宽度优先搜索算法可以找到最短路径，因此在解决迷宫问题时更为常用。

下面是一个Python实现的迷宫宽度优先搜索算法的示例代码：

n, m = 5, 5
lines = ['0 1 0 0 0', '0 1 0 1 0', '0 0 0 0 0', '0 1 1 1 0', '0 0 0 1 0']
grids = []
for i in range(n):
    grids.append(list(map(int, lines[i].split())))

move = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def bfs():
    global n, m
    queue = [0]*(n*m)
    hh, tt = 0, 0
    queue[0] = [0, 0]
    res = 0
    grids[0][0] = -1
    while hh <= tt:
        res += 1
        for i in range(hh, tt+1):
            x, y = queue[hh]; hh += 1
            for oi, oj in move:
                xi, yj = x + oi, y + oj
                if not 0 <= xi < n or not 0 <= yj < m:
                    continue
                if grids[xi][yj] == 1 or grids[xi][yj] == -1:
                    continue
                if xi == n-1 and yj == m-1:
                    return res
                tt += 1
                queue[tt] = [xi, yj]
                grids[xi][yj] = -1

print(bfs())

该代码中，我们首先定义了一个5x5的迷宫，然后定义了一个move数组，用于表示可以移动的方向。在bfs函数中，我们使用队列来实现宽度优先搜索。我们首先将起点加入队列中，并将起点标记为已访问。然后，我们不断从队列中取出节点，并将其周围未访问过的节点加入队列中。如果我们找到了终点，就返回当前步数。如果队列为空，说明无法到达终点，返回-1。