数据结构——BFS广度优先遍历之走迷宫

import numpy as np
from queue import Queue
def main():
    global g, q, d,n,m
    n = int(input("请输入n值："))
    m = int(input("请输入m值："))

    global g,q,d
    g = np.zeros((n,m),dtype=int) # 存放迷宫
    q = Queue(0) # 队列
    d = np.full((n,m),-1,dtype=int) # 走了多少

    for i in range(n):
        print("请输入第{}行:".format(i))
        for j in range(m):
            g[i][j] = int(input("请输入第{}个数值".format(j)))
    print(g)
    print(bfs())
    print(g)

def bfs():
    d[0][0] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1] # 上下左右
    q.put([0,0]) # 队列加入起点
    # 遍历四种可行路线

    while q.qsize():
        t = q.get()
        for i in range(4):
            x = t[0] + dx[i]
            y = t[1] + dy[i]

            if x>=0 and x<n and y>=0 and y<m and g[x][y] != 1 and d[x][y] == -1:
                d[x][y] = d[t[0]][t[1]]+1
                q.put([x,y])

    return d[n-1][m-1]


if __name__ == '__main__':
    main()