Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
# @njit((i8,i8,i8), cache=True)
@njit(cache=True)
def pos(W,h,w):
    return h * W + w

# @njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
@njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)



Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, i1, i4, i8, f8
# @njit((i8,i8), cache=True)
@njit(cache=True)
def pos(h,w):
    return h * W + w

# @njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
@njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(*e)]:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(*e)] > dist[pos(*x)] + cost:
                    dist[pos(*e)] = dist[pos(*x)] + cost
                    heapq.heappush(hq,(dist[pos(*e)],e))

    # print(dist)
    if dist[pos(*t)] == INF: 
        dist[pos(*t)] = -1
        
    return dist[pos(*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,G)
    print(ans)



Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#! /usr/bin/env python3
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = []
    for i in range(H):
        S=list(input())
        G.append(S)

    mx = H*W
    edge = defaultdict(lambda: [])
    

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = []
    heapq.heappush(hq,(0,s))

    dist = defaultdict(lambda: INF) # sからxでの最短距離
    dist[s] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue
        
        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#":  continue
                if e in normal:
                    cost -= 1
                
                if dist[e] > dist[x] + cost:
                    dist[e] = dist[x] + cost
                    heapq.heappush(hq,(dist[e],e))

    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()



Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#! /usr/bin/env python3
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = []
    for i in range(H):
        S=list(input())
        G.append(S)

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

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue
            normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    edge[(h,w)].append(((new_h,new_w),cost))
                    # edge[y].append((x,cost))
    

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = []
    heapq.heappush(hq,(0,s))

    dist = defaultdict(lambda: INF) # sからxでの最短距離
    dist[s] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()



Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#! /usr/bin/env python3
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = []
    for i in range(H):
        S=list(input())
        G.append(S)

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

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    edge[(h,w)].append(((new_h,new_w),cost))
                    # edge[y].append((x,cost))
    

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = []
    heapq.heappush(hq,(0,s))

    dist = defaultdict(lambda: INF) # sからxでの最短距離
    dist[s] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()



Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = []
    for i in range(H):
        S=list(input())
        G.append(S)

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

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = []
    heapq.heappush(hq,(0,s))

    INF = 10**9

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = []
    for i in range(H):
        S=list(input())
        G.append(S)

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

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    INF = 10**9

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

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

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    INF = 10**9

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

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

    mx = H*W
    edge = defaultdict(lambda: [])

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    # edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

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

    mx = H*W
    edge = [[] for _ in range(mx)]

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            normal = [(h-1,w),(h+1,w),(h,w+1),(h,w-1)]
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    cost = 1

                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    if (new_h,new_w) in normal:
                        cost -= 1
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,cost))
                    edge[y].append((x,cost))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

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

    mx = H*W
    edge = [[] for _ in range(mx)]
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_h,new_w = h+dh,w+dw
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#": continue

                y = pos(new_h,new_w)
                edge[x].append((y,0))
                edge[y].append((x,0))
                    
 
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    y = pos(new_h,new_w)
                    edge[x].append((y,1))
                    edge[y].append((x,1))
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e,cost in edge[x]:
            if dist[e] > dist[x] + cost:
                dist[e] = dist[x] + cost
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

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

    mx = H*W
    cost = [[INF] * mx for _ in range(mx)]
    edge = [[] for _ in range(mx)]
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_h,new_w = h+dh,w+dw
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#": continue

                y = pos(new_h,new_w)
                cost[x][y] = 0
                cost[y][x] = 0
                edge[x].append(y)
                edge[y].append(x)
                    
 
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    y = pos(new_h,new_w)
                    cost[x][y] = min(cost[x][y],1)
                    cost[y][x] = min(cost[y][x],1)
                    edge[x].append(y)
                    edge[y].append(x)
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e in edge[x]:
            if dist[e] > dist[x] + cost[x][e]:
                dist[e] = dist[x] + cost[x][e]
                heapq.heappush(hq,(dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

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

    mx = H*W
    cost = [[INF] * mx for _ in range(mx)]
    edge = [[] for _ in range(mx)]
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_h,new_w = h+dh,w+dw
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#": continue

                y = pos(new_h,new_w)
                cost[x][y] = 0
                cost[y][x] = 0
                edge[x].append(y)
                edge[y].append(x)
                    
 
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    y = pos(new_h,new_w)
                    cost[x][y] = min(cost[x][y],1)
                    cost[y][x] = min(cost[y][x],1)
                    edge[x].append(y)
                    edge[y].append(x)
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e in edge[x]:
            if dist[e] > dist[x] + cost[x][e]:
                dist[e] = dist[x] + cost[x][e]
                hq.append((dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)