Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Runtime Error):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0

    dx_dys = [ [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 1]
             , [-1, 2], [0, -2], [0, 2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2],
             [2, -1], [2, 0], [2, 1], [2, 2] ]

    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):
            """
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
            """
            for dx_dy in dx_dys:
                dx, dy = dx_dy[0], dx_dy[1]
                next = [x+ dx, y+ dy]
                if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                    dists[next[1] ][next[0] ] = dists[y][x]+1
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0
            
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0], 0]) # [dist, x, y, neighbour_only]
    # neighbour_only: 0 -> T, 1-4 -> L, R, D, U, 5-> All
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        if(dist_pos[3] == 0):
            for dx, dy, i in ( (-1, 0, 1), (1, 0, 2), (0, -1, 3), (0, 1, 4) ):
                if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                    continue
                if(Maps[y+dy][x+dx]=="#"):
                    Flag = i
                    N_Flag += 1
                    continue

                next = [x+ dx, y+ dy]
                #print([x, y], next)
                if(dists[next[1] ][next[0] ] > dists[y][x]):
                    dists[next[1] ][next[0] ] = dists[y][x]
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])
            if(N_Flag >1):
                heapq.heappush(deque, [ dists[y][x], x, y, 5 ])
            elif(N_Flag > 0):
                heapq.heappush(deque, [ dists[y][x], x, y, Flag ])
        elif(dist_pos[3] == 5):
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])

        else:
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(dist_pos[3] == 4):
                dy_min = 1
            elif(dist_pos[3] == 3):
                dy_max = 0
            elif(dist_pos[3] == 2):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Runtime Error):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0], 0]) # [dist, x, y, neighbour_only]
    # neighbour_only: 0 -> T, 1-4 -> L, R, D, U, 5-> All
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        if(dist_pos[3] == 0):
            for dx, dy, i in ( (-1, 0, 1), (1, 0, 2), (0, -1, 3), (0, 1, 4) ):
                if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                    continue
                if(Maps[y+dy][x+dx]=="#"):
                    Flag = i
                    N_Flag += 1
                    continue

                next = [x+ dx, y+ dy]
                #print([x, y], next)
                if(dists[next[1] ][next[0] ] > dists[y][x]):
                    dists[next[1] ][next[0] ] = dists[y][x]
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])
            if(N_Flag >1):
                heapq.heappush(deque, [ dists[y][x], x, y, 5 ])
            elif(N_Flag > 0):
                heapq.heappush(deque, [ dists[y][x], x, y, Flag ])
        elif(dist_pos[3] == 5):
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])

        else:
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(dist_pos[4] == 3):
                dy_min = 1
            elif(dist_pos[3] == 2):
                dy_max = 0
            elif(dist_pos[2] == 1):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = [False]*4 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag[i] = True
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):
            for dy in range( max(-y, -2), min(H-y, 3) ):
                for dx in range( max(-x, -2), min(W-x, 3) ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] > dists[y][x]+1):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag[3] == True):
                dy_min = 1
            elif(Flag[2] == True):
                dy_max = 0
            elif(Flag[1] == True):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] > dists[y][x]+1):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = False
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = True
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(Flag==True):
            for dy in range( max(-y, -2), min(H-y, 3) ):
                for dx in range( max(-x, -2), min(W-x, 3) ):
                    next = [x+ dx, y+ dy]
                    if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
        


    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = [ [False]*3 for _ in range(3) ]
        N_Flag = 0
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag[dy+1][dx+1] = True
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>0):
            if(N_Flag > 1):
                for dy in range( max(-y, -2), min(H-y, 3) ):
                    for dx in range( max(-x, -2), min(W-x, 3) ):
                        next = [x+ dx, y+ dy]
                        if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                            dists[next[1] ][next[0] ] = dists[y][x]+1
                            heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
            else:
                dy_max = min(H-y, 3)
                dy_min = max(-y, -2)
                dx_min = max(-x, -2)
                dx_max = min(W-x, 3)
                if(Flag[2][1] == True):
                    dy_min = 1
                elif(Flag[0][1] == True):
                    dy_max = 0
                elif(Flag[1][2] == True):
                    dx_min = 1
                else:
                    dx_max = 0
                for dy in range( dy_min, dy_max ):
                    for dx in range( dx_min, dx_max ):
                        next = [x+ dx, y+ dy]
                        if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                            dists[next[1] ][next[0] ] = dists[y][x]+1
                            heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = [ [False]*3 for _ in range(3) ]
        N_Flag = 0
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag[dy+1][dx+1] = True
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>0):
            if(N_Flag > 1):
                for dy in range( max(-y, -2), min(H-y, 3) ):
                    for dx in range( max(-x, -2), min(W-x, 3) ):
                        next = [x+ dx, y+ dy]
                        if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                            dists[next[1] ][next[0] ] = dists[y][x]+1
                            heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
            else:
                dy_max = min(H-y, 3)
                dy_min = max(-y, -2)
                dx_min = max(-x, -2)
                dx_max = min(W-x, 3)
                if(Flag[2][1] == True):
                    dy_min = 1
                elif(Flag[0][1] == True):
                    dy_max = 0
                elif(Flag[1][2] == True):
                    dx_min = 1
                else:
                    dx_max = 0
                for dy in range( dy_min, dy_max ):
                    for dx in range( dx_min, dx_max ):
                        next = [x+ dx, y+ dy]
                        if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                            dists[next[1] ][next[0] ] = dists[y][x]+1
                            heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = False
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = True
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(Flag):
            for dy in range( max(-y, -2), min(H-y, 3) ):
                for dx in range( max(-x, -2), min(W-x, 3) ):
                    next = [x+ dx, y+ dy]
                    if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
        
    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+2, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+2, x) ):
            if(Mazes[i][j] == "."):
                flag_searched[i][j] = True
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    road_types = []
    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1 or Maps[y+dy][x+dx]=="#"):
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        for dy in range( max(-y, -2), min(H-y, 3) ):
            for dx in range( max(-x, -2), min(W-x, 3) ):
                next = [x+ dx, y+ dy]
                if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                    dists[next[1] ][next[0] ] = dists[y][x]+1
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+2, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+2, x) ):
            if(Mazes[i][j] == "."):
                flag_searched[i][j] = True
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    road_types = []
    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    #print(road_types)
    for i in range(H):
        for j in range(W):
            if(Maps[i][j] == "#" and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                check(Maps, flag_searched, parents, j, i, Edges, road_types)
            """
            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types)

                for dy in range(-2, 3, 1):
                    for dx in range(-2, 3, 1):
                        if(-1< i+dy and i+dy < H and -1< j+dx and j+dx < W and flag_searched[i+dy][j+dx]==False):
                            flag_searched[i+dy][j+dx] = True

                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)
            """
    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)






if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    road_types = []
    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]
    for i in range(H):
        for j in range(W):
            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                for dy in range(-2, 3, 1):
                    for dx in range(-2, 3, 1):
                        if(-1< i+dy and i+dy < H and -1< j+dx and j+dx < W and flag_searched[i+dy][j+dx]==False):
                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)
    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])


Fixed submission:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """