题解 | #走迷宫#

"""
import heapq
from collections import defaultdict

ins=[]
while True:
    try:
        ins.append(list(input().split()))
    except:
        break

def pre_data(ins):
    n,m=[int(val) for val in ins[0]]
    xs,ys,xt,yt=[int(val) for val in ins[1]]
    data=ins[2:]

    edges=defaultdict(list)
    for ni in range(n):
        for mi in range(m):
            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            #for x,y in [(1,0),(0,1)]:
                #print ('xy',x,y)
                if ni+x >= 0 and ni+x<n and mi+y>=0 and mi+y<m:
                    if data[ni][0][mi]=='.' and data[ni+x][0][mi+y]=='.':
                        edges[ni*m+(mi+1)].append(((ni+x)*m+(mi+y+1),1))
                        #edges[(ni+x)*m+(mi+y+1)].append((ni*m+(mi+1),1))

    #print ('edges',edges)
    si=(xs-1)*m+(ys+0)
    ei=(xt-1)*m+(yt+0)
    flag=0
    if data[xt-1][0][yt-1]=='*':
        flag=1
    
    #print ('*',flag)
    return n,m,si,ei,flag,edges


def min_cost(n,m,si,ei,flag,edges):
    if flag:
        return -1

    visited=[0]*(n*m+1)
    
    alls=[(0,si)]#cost,node

    while alls:
        cost,node=heapq.heappop(alls)
        if visited[node]==1:
            continue
        if node==ei:
            return cost
        visited[node]=1

        for nbi,costi in edges[node]:
            if visited[nbi]==0:
                heapq.heappush(alls,(costi+cost,nbi))
    
    return -1

if __name__=='__main__':
    n,m,si,ei,flag,edges=pre_data(ins)
    print (min_cost(n,m,si,ei,flag,edges))
"""

ins = []
while True:
    try:
        ins.append(list(input().split()))
    except:
        break


def min_cost_bfs(ins):
    n, m = [int(val) for val in ins[0]]
    xs, ys, xt, yt = [int(val) for val in ins[1]]
    data = ins[2:]

    alls=[(xs-1,ys-1,0)]
    visited=[[0]*m for _ in range(n)]
    
    while alls:
        x,y,cost=alls.pop(0)
        if x==xt-1 and y==yt-1:
            return cost
        if visited[x][y]:
            continue
        visited[x][y]=1

        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            xi,yi=x+dx,y+dy
            if xi>=0 and xi<n and yi>=0 and yi<m:
                if visited[xi][yi]==0 and data[xi][0][yi]=='.':
                    alls.append((xi,yi,1+cost))


    return -1

if __name__ == "__main__":
    print(min_cost_bfs(ins))

第一个解法dfs，第二个bfs。第二个时间复杂度低。