关于#python#的bfs算法问题，如何解决？

洛谷P1746 离开中山路，这用python用bfs怎么做a，我做了报了四五个超时，怎么优化呢

from collections import deque
n=int(input())
ddd=[]
for i in range(n):
    ddd.append(input())
x1,y1,x2,y2=map(int,input().split())
wod=[[0]*n for i in range(n)]
queue=deque()
queue.append((x1-1,y1-1))
xx=[0,1,0,-1]
yy=[1,0,-1,0]
while queue:
    if queue[0][0]==x2-1 and queue[0][1]==y2-1:
        print(wod[queue[0][0]][queue[0][1]])
        break
    di,gi=queue.popleft()
    for i in range(4):
        dd=di+xx[i]
        gg=gi+yy[i]
        if dd>=0 and dd<=n-1 and gg>=0 and gg<=n-1 and ddd[dd][gg]!='1' and wod[dd][gg]==0:
            wod[dd][gg]=wod[di][gi]+1
            queue.append((dd,gg))