题解 | #走迷宫#

from math import inf
from collections import deque
import sys

n,m = map(int,input().split())    #网格大小
xs,ys,xt,yt = map(int,input().split())
xs,ys,xt,yt =xs-1,ys-1,xt-1,yt-1
# arr[0]----->起点x坐标 arr[1]----->起点y坐标  arr[2]----->终点x坐标  arr[3]----->终点y坐标

d = []    # 迷宫
map_list = [[inf for _ in range(m)] for _ in range(n)]  #邻接矩阵
open_list = deque([])  #未搜索列表
visited = set()  # 已搜索表

for i in range(n):
    d.append(input())

map_list[xs][ys] = 0
open_list.append([xs,ys])
def search_four(n,m,a,map_list,d,xt,yt):
    cost = map_list[a[0]][a[1]]
    visited.add((a[0],a[1]))
    for [u,v] in [[0,1],[0,-1],[1,0],[-1,0]]:
        x = a[0]+u
        y = a[1]+v
        if x==xt and y==yt:
            map_list[x][y] = 1+cost
        elif 0 <= x <n and 0 <= y < m and d[x][y]!='*' and (x,y) not in visited:
                map_list[x][y] = 1+cost
                open_list.append([x,y])    
                visited.add((x,y))
    return map_list


# 从起点开始搜索，搜索上下左右四个方向,如果有点的话，就将cost+1记录下来，并且标记起点为已经搜索过(已完成)
# 将未搜索过的点按照cost的大小排列，取出cost最小的点（弹出最左边代替排序）
# 从这个cost最小的点开始搜索，搜索上下左右四个方向，如果存在这个点并且这个点没有被搜索过，那就将cost+1作为它的代价记录下来，并且标记之前cost最小的点搜索过，如果上下左右的点有的点已经有cost了，比较大小取最小的那个值作为cost保存下来(已完成)
# 循环操作步骤2和3。直到已经搜索到终点，即终点的cost有值了，就结束；或者是已经没有点需要被搜索了，还没有找到终点，那么就是没有相关的路径（已完成）
count = map_list[xt][yt]
if d[xt][yt]=='*':
    print(-1)
else:
    while open_list and count==inf:
        a = open_list.popleft()
        search_four(n,m,a,map_list,d,xt,yt)
        count = map_list[xt][yt]

    if count ==inf:
        print(-1)
    else:
        print(count)

本来想用D算法，写着写着发现不用那么复杂，BFS算法就可以，注意点就是：字典的问题，还有减枝，在同一层的点不用遍历两次