Buggy python submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
assert False
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from queue import deque 
q = deque([(0, start)]) # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = q.popleft()
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            if vv==0:
                q.appendleft((num, u))
            else:
                q.append((num,u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
        
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
        
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = (ch,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,(ux,uy) = hpp(q)
    if (ux,uy)==goal:
        break
#     print(ux,uy, num, prv)
    for xx,yy,vv in zip(dx,dy,vvs):
        x = ux+xx
        y = uy+yy
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue            
        if seen[x*w+y] is None or seen[x*w+y]>num:
            seen[x*w+y] = num
            hp(q, (num, (x,y)))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = (ch,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,(ux,uy) = hpp(q)
#     print(ux,uy, num, prv)
    for xx,yy,vv in zip(dx,dy,vvs):
        x = ux+xx
        y = uy+yy
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue            
        if seen[x*w+y] is None or seen[x*w+y]>num:
            seen[x*w+y] = num
            hp(q, (num, (x,y)))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)