Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()


Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    l1=list(range(w))
    l2=list(range(-2,3))
    for i in range(h):
        for j in l1:
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in l2:
                for dy in l2:
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in {(-1,0),(0,-1),(1,0),(0,1)}:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()


Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in {(-1,0),(0,-1),(1,0),(0,1)}:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()


Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        #始点sから各頂点への最短距離
        d = [10**18] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()


Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
def main():
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        #始点sから各頂点への最短距離
        d = [10**18] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                            edge[idx].append((0,idx1))
                        else:
                            edge[idx].append((1,idx1))
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()


Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
def main():
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        #始点sから各頂点への最短距離
        d = [10**18] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,[e[0]+d[v],e[1]])
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                            edge[idx].append([0,idx1])
                        else:
                            edge[idx].append([1,idx1])
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#ダイクストラ法
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [10**18] * h*w
    used = [True] * h*w #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
ch-=1
cw-=1
dh-=1
dw-=1
s=[input() for _ in range(h)]
edge=[[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        idx=i*w+j
        for dx in range(-2,3):
            for dy in range(-2,3):
                nx=i+dx
                ny=j+dy
                if 0<=nx<h and 0<=ny<w:
                    idx1=nx*w+ny
                    if dx==0 and dy==0:
                        continue
                    if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                        edge[idx].append([0,idx1])
                    else:
                        edge[idx].append([1,idx1])
s=ch*w+cw
g=dh*w+dw
d=dijkstra_heap(s)
ans=d[g]
if ans==10**18:
    print(-1)
else:
    print(ans)

Fixed submission:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()