猫史档案馆

 

 

能帮助你知道一个迷宫最快需要多少步走出

n,m = int(input('请输入迷宫的行数')),int(input('请输入迷宫的列数'))
lst=[]
z=0
for i in range(n):
    z+=1
    print('请输入迷宫的第',z,'行，注：请将可行走的格子用英文句号（.）来表示，障碍物用英文（#）来表示')
    lst.append(list(input()))
q=[]
v=[[0]* m for i in range(n)]
end_x,end_y=2, 4
q.append([0,0,0])
v[0][0] = 1
while q:
    x,y,step=q.pop(0)
    if x == end_x and y == end_y:
        print('最快需要',step,'步')
        break
    x_u = x - 1
    y_u = y
    if x_u >= 0 and v[x_u][y_u] ==0 and lst[x_u][y_u] != '#':
        q.append([x_u,y_u,step+1])
        v[x_u][y_u] = 1
    x_d = x + 1
    y_d = y
    if x_d < n and v[x_d][y_d] == 0 and lst[x_d][y_d] != '#':
        q.append([x_d, y_d, step+1])
        v[x_d][y_d] = 1
    x_left = x
    y_left = y - 1
    if y_left >= 0 and v[x_left][y_left] == 0 and lst[x_left][y_left] != '#':
        q.append([x_left, y_left, step+1])
        v[x_left][y_left] = 1
    x_right = x
    y_right = y + 1
    if y_right < m and v[x_right][y_right] == 0 and lst[x_right][y_right] != '#':
        q.append([x_right, y_right, step+1])
        v[x_right][y_right] = 1
else:
    print('无法走出此迷宫')