python版BFS样例输出13,搜到的不是最短路
查看原帖
python版BFS样例输出13,搜到的不是最短路
628578
192210304230wgd楼主2022/2/8 18:23
import queue
import copy

N,M=map(int,input().split())
ditu=[list(map(int,input().split()))for i in range(N)]#获得的是格的地图
move=[[3,0],[0,-3],[-3,0],[0,3],[2,0],[0,-2],[-2,0],[0,2],[1,0],[0,-1],[-1,0],[0,1]]
dir=['S','W','N','E']
dirdict={'S':'N','N':'S','W':'E','E':'W'}

vis=copy.deepcopy(ditu)#建立点的地图
for i in range(len(vis)):
    vis[i].append(0)
temp=[0]*(M+1)
vis.append(temp)
for i in range(N):
    for j in range(M):
        if ditu[i][j]==1:
            vis[i+1][j]=1
            vis[i+1][j+1] = 1
            vis[i][j+1] = 1

x,y,mx,my,s=input().split()
x,y,mx,my=int(x),int(y),int(mx),int(my)
q=queue.Queue()
q.put((x,y,s,0))
vis[x][y]=1
ans=-1

while q.empty()==False:
    now=q.get()
    if now[0]==mx and now[1]==my:
        ans=now[3]
        break
    for i in range(12):
        if i==0 or i==1 or i==2 or i==3:#可能会穿墙,需要特判
            temp1=now[0]+move[i+4][0]
            temp2=now[1]+move[i+4][1]
            if temp1>0 and temp1<N and temp2>0 and temp2<M and vis[temp1][temp2]!=0:
                continue
        newx=now[0]+move[i][0]
        newy=now[1]+move[i][1]
        newstep = now[3] + 1
        newdir = dir[i%4]
        if newdir!=now[2]:#看是否需要转向
            if newdir==dirdict[now[2]]:
                newstep+=2
            else:
                newstep+=1
        if newx>0 and newx<N and newy>0 and newy<M and vis[newx][newy]==0:
            vis[newx][newy] =1
            q.put((newx,newy,newdir,newstep))

print(ans)
2022/2/8 18:23
加载中...