""" 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。第二个时间复杂度低。