Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    adj=[(-1,0), (0,1), (1,0), (0,-1)]
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]=='#':
                continue
            for dh in range(-2,3):
                for dw in range(-2,3):
                    if dh==0 and dw==0:
                        continue
                    h_dst=h+dh
                    w_dst=w+dw
                    
                    if (0<=h_dst<H) and (0<=w_dst<W) and (Ss[h_dst][w_dst]=='.'):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            #graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            #graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    #Ss.append([(1 if c=='.'else 0) for c in input()])
    Ss.append(input())
main()

Fixed submission:
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    adj=[(-1,0), (0,1), (1,0), (0,-1)]
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]=='#':
                continue
            for dh in range(-2,3):
                for dw in range(-2,3):
                    if dh==0 and dw==0:
                        continue
                    h_dst=h+dh
                    w_dst=w+dw
                    
                    if (0<=h_dst<H) and (0<=w_dst<W) and (Ss[h_dst][w_dst]=='.'):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            #graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            #graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    #Ss.append([(1 if c=='.'else 0) for c in input()])
    Ss.append(input())
main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]==0:
                continue
            adj=[(-1,0), (0,1), (1,0), (0,-1)]
            for dh in [-2,-1, 0, 1, 2]:
                for dw in [-2, -1, 0, 1, 2]:
                    h_dst=h+dh
                    w_dst=w+dw
                    if (0<=h_dst<H) and (0<=w_dst<W) and (dh!=0 or dw!=0) and (Ss[h_dst][w_dst]==1):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    Ss.append([(1 if c=='.'else 0) for c in input()])
main()

Fixed submission:
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    adj=[(-1,0), (0,1), (1,0), (0,-1)]
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]=='#':
                continue
            for dh in range(-2,3):
                for dw in range(-2,3):
                    if dh==0 and dw==0:
                        continue
                    h_dst=h+dh
                    w_dst=w+dw
                    
                    if (0<=h_dst<H) and (0<=w_dst<W) and (Ss[h_dst][w_dst]=='.'):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            #graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            #graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    #Ss.append([(1 if c=='.'else 0) for c in input()])
    Ss.append(input())
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def idx(h,w):
    return h*W + w

def main():
    row=[]
    col=[]
    data=[]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]==0:
                continue
            adj=[(-1,0), (0,1), (1,0), (0,-1)]
            #for dp in [(-1,0), (0,1), (1,0), (0,-1)]:
            #    dh,dw = dp
            #    h_dst=h+dh
            #    w_dst=w+dw
            #    if (0<= h_dst <H) and (0<= w_dst<W) and (Ss[h_dst][w_dst]==1):
            #        row.append(idx_from)
            #        col.append(idx(h_dst,w_dst))
            #        data.append(0)
            for dh in [-2,-1, 0, 1, 2]:
                for dw in [-2, -1, 0, 1, 2]:
                    h_dst=h+dh
                    w_dst=w+dw
                    if (0<=h_dst<H) and (0<=w_dst<W) and (dh!=0 or dw!=0) and (Ss[h_dst][w_dst]==1):
                        row.append(idx_from)
                        col.append(idx(h_dst,w_dst))
                        if (dh,dw) in adj:
                            data.append(1)
                        else:
                            data.append(10**6)
    row=np.array(row)
    col=np.array(col)
    data=np.array(data)
    graph=csr_matrix((data,(row,col)), shape=(N,N))
    #print(graph.toarray())

    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=idx(Ch,Cw), return_predecessors=False)
    #print(dist_matrix)
    #print(predecessors)
    #print(dist_matrix[idx(Dh,Dw)])
    ans=dist_matrix[idx(Dh,Dw)]
    ans=-1 if ans==np.inf else int(ans)//10**6

    print(ans)


H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    Ss.append([(1 if c=='.'else 0) for c in input()])
main()

Fixed submission:
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    adj=[(-1,0), (0,1), (1,0), (0,-1)]
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]=='#':
                continue
            for dh in range(-2,3):
                for dw in range(-2,3):
                    if dh==0 and dw==0:
                        continue
                    h_dst=h+dh
                    w_dst=w+dw
                    
                    if (0<=h_dst<H) and (0<=w_dst<W) and (Ss[h_dst][w_dst]=='.'):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            #graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            #graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    #Ss.append([(1 if c=='.'else 0) for c in input()])
    Ss.append(input())
main()

Buggy python submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def idx(h,w):
    return h*W + w

def main():
    row=[]
    col=[]
    data=[]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]==0:
                continue
            adj=[(-1,0), (0,1), (1,0), (0,-1)]
            #for dp in [(-1,0), (0,1), (1,0), (0,-1)]:
            #    dh,dw = dp
            #    h_dst=h+dh
            #    w_dst=w+dw
            #    if (0<= h_dst <H) and (0<= w_dst<W) and (Ss[h_dst][w_dst]==1):
            #        row.append(idx_from)
            #        col.append(idx(h_dst,w_dst))
            #        data.append(0)
            for dh in [-2,-1, 0, 1, 2]:
                for dw in [-2, -1, 0, 1, 2]:
                    h_dst=h+dh
                    w_dst=w+dw
                    if (0<=h_dst<H) and (0<=w_dst<W) and (dh!=0 or dw!=0) and (Ss[h_dst][w_dst]==1):
                        row.append(idx_from)
                        col.append(idx(h_dst,w_dst))
                        if (dh,dw) in adj:
                            data.append(1)
                        else:
                            data.append(10**6)
    row=np.array(row)
    col=np.array(col)
    data=np.array(data)
    graph=csr_matrix((data,(row,col)), shape=(N,N))
    #print(graph.toarray())

    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=idx(Ch,Cw), return_predecessors=False)
    #print(dist_matrix)
    #print(predecessors)
    #print(dist_matrix[idx(Dh,Dw)])
    ans=dist_matrix[idx(Dh,Dw)]
    ans=-1 if ans==np.inf else int(ans)//10**6

    print(ans)


H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    Ss.append([(1 if c=='.'else 0) for c in input()])
main()

Fixed submission:
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    adj=[(-1,0), (0,1), (1,0), (0,-1)]
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]=='#':
                continue
            for dh in range(-2,3):
                for dw in range(-2,3):
                    if dh==0 and dw==0:
                        continue
                    h_dst=h+dh
                    w_dst=w+dw
                    
                    if (0<=h_dst<H) and (0<=w_dst<W) and (Ss[h_dst][w_dst]=='.'):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            #graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            #graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    #Ss.append([(1 if c=='.'else 0) for c in input()])
    Ss.append(input())
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def idx(h,w):
    return h*W + w

def main():
    row=[]
    col=[]
    data=[]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]==0:
                continue
            adj=[(-1,0), (0,1), (1,0), (0,-1)]
            #for dp in [(-1,0), (0,1), (1,0), (0,-1)]:
            #    dh,dw = dp
            #    h_dst=h+dh
            #    w_dst=w+dw
            #    if (0<= h_dst <H) and (0<= w_dst<W) and (Ss[h_dst][w_dst]==1):
            #        row.append(idx_from)
            #        col.append(idx(h_dst,w_dst))
            #        data.append(0)
            for dh in [-2,-1, 0, 1, 2]:
                for dw in [-2, -1, 0, 1, 2]:
                    h_dst=h+dh
                    w_dst=w+dw
                    if (0<=h_dst<H) and (0<=w_dst<W) and (dh!=0 or dw!=0) and (Ss[h_dst][w_dst]==1):
                        row.append(idx_from)
                        col.append(idx(h_dst,w_dst))
                        if (dh,dw) in adj:
                            data.append(1)
                        else:
                            data.append(10**6)
    row=np.array(row)
    col=np.array(col)
    data=np.array(data)
    graph=csr_matrix((data,(row,col)), shape=(N,N))
    #print(graph.toarray())

    dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=idx(Ch,Cw), return_predecessors=True)
    #print(dist_matrix)
    #print(predecessors)
    #print(dist_matrix[idx(Dh,Dw)])
    ans=dist_matrix[idx(Dh,Dw)]
    ans=-1 if ans==np.inf else int(ans)//10**6

    print(ans)


H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    Ss.append([(1 if c=='.'else 0) for c in input()])
main()

Fixed submission:
from collections import deque

def idx(h,w):
    return h*W + w

def main():
    adj=[(-1,0), (0,1), (1,0), (0,-1)]
    graph=[set() for _ in range(N)]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]=='#':
                continue
            for dh in range(-2,3):
                for dw in range(-2,3):
                    if dh==0 and dw==0:
                        continue
                    h_dst=h+dh
                    w_dst=w+dw
                    
                    if (0<=h_dst<H) and (0<=w_dst<W) and (Ss[h_dst][w_dst]=='.'):
                        idx_to=idx(h_dst,w_dst)
                        if (dh,dw) in adj:
                            graph[idx_from].add((idx_to,0))
                            #graph[idx_to].add((idx_from,0))
                        else:
                            graph[idx_from].add((idx_to,1))
                            #graph[idx_to].add((idx_from,1))
    s=idx(Ch,Cw)
    dist=[10**9]*N
    dist[s]=0
    que=deque()
    que.append(s)

    while len(que)>0:
        i = que.popleft() # 先頭取り出し
        for j,c in graph[i]:
            d = dist[i] + c
            if d < dist[j]:
                dist[j] = d
                if c == 1:
                    que.append(j) # 末尾へ
                else:
                    que.appendleft(j) #先頭へ
    #print(graph,dist)
    ans = dist[idx(Dh,Dw)]
    print(-1 if ans == 10**9 else ans)

H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    #Ss.append([(1 if c=='.'else 0) for c in input()])
    Ss.append(input())
main()