Problem p02579 (python)

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 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]])

Buggy 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]])