Problem p02579 (python)

Fixed submission:
#01BFS

H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def in_area(x,y):
    return 0<=x<=H-1 and 0<=y<=W-1
    
def cango_step(x,y):
    cand0 =[(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

def cango_warponly(x,y):
    cand0 =[(x-2,y-2),(x-2,y-1),(x-2,y),(x-2,y+1),(x-2,y+2),
            (x+2,y-2),(x+2,y-1),(x+2,y),(x+2,y+1),(x+2,y+2),
            (x+1,y-2),(x,y-2),(x-1,y-2),
            (x+1,y+2),(x,y+2),(x-1,y+2),
            (x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

q = deque([(-1,-1,CH-1,CW-1,0)]) 
been = [[False]*W for _ in range(H)]
INF=10**20
shortest =[[INF]*W for _ in range(H)]
shortest[CH-1][CW-1] = 0
    
reach=False
while q:
    x_old,y_old,x_now,y_now,time = q.pop()
    #print(x_now,y_now,time)
    
#     if x_now==H-1 and y_now==W-1:
#         reach=True
#         break
        
    cand = cango_step(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time:
            q.append((x_now,y_now,x_new,y_new,time))
            shortest[x_new][y_new]=time
            
    cand = cango_warponly(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time+1:
            q.appendleft((x_now,y_now,x_new,y_new,time+1))
            shortest[x_new][y_new]=time+1
            
if shortest[DH-1][DW-1]==INF:
    print(-1)
else:
    print(shortest[DH-1][DW-1])

Buggy submission (verdict: Runtime Error):
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def cango_step(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
def cango_warp(x,y):
    cand = [(i,j) 
            for i in range(x-2,x+3) for j in range(y-2,y+3) 
            if 0<=i and i<=H-1 and 0<=j and j<=W-1]
    return cand

been = [[False]*W for _ in range(H)]
rooms=dict()
i_room=-1
for x in range(H):
    for y in range(W):
        if S[x][y]=="." and not been[x][y]:
            i_room+=1
            been[x][y]=True
            q = deque([(-1,-1,x,y)]) 

            rooms[(x,y)]=i_room
            while q:
                x_old,y_old,x_now,y_now = q.popleft()
                
                cand = cango_step(x_now,y_now)
                #print(x_old,y_old,x_now,y_now,time)
                
                if x_now==CH-1 and y_now==CW-1:
                    start_warp = i_room
                if x_now==DH-1 and y_now==DW-1:
                    end_warp = i_room
                
                for x_new,y_new in cand:
                    if not been[x_new][y_new] and S[x_new][y_new]==".":
                        q.append((x_now,y_now,x_new,y_new))
                        been[x_new][y_new]=True
#                        room.append((x_new,y_new))
                        rooms[(x_new,y_new)]=i_room
#            rooms.append(room)

if start_warp==end_warp:
    print(0)
else:
        
    #ワープで行けるほかの部屋をtree入れる
    n_rooms = i_room+1
    tree=[[] for _ in range(n_rooms)]
    
    i_loop=0
    for k,v in rooms.items():
        i_loop+=1
        cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
        for c in cango:
            if c!=v:
                tree[c].append(v)
                tree[v].append(c)
        if i_loop%1000==0:
            for i in range(len(tree)):
                tree[i] = set(tree[i])
        #print(v,cango)

        
    for i in range(len(tree)):
        tree[i] = set(tree[i])
    
    
    q = deque([(-1,start_warp,0)]) #これでもよい
    
    been=[False]*n_rooms
    been[start_warp]=True
    reach=False
    while q:
        parent,x,time = q.popleft()
        if x==end_warp:
            reach=True
            break
        
        for y in tree[x]:
            if not been[y]:
                q.append((x,y,time+1))#子ノードを追加
                been[y]=True
        #print(parent,x,q,time)
    if reach:
        print(time)
    else:
        print(-1)

Buggy submission (verdict: Runtime Error):
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def cango_step(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
def cango_warp(x,y):
    cand = [(i,j) 
            for i in range(x-2,x+3) for j in range(y-2,y+3) 
            if 0<=i and i<=H-1 and 0<=j and j<=W-1]
    return cand

been = [[False]*W for _ in range(H)]
rooms=dict()
i_room=-1
for x in range(H):
    for y in range(W):
        if S[x][y]=="." and not been[x][y]:
            i_room+=1
            been[x][y]=True
            q = deque([(-1,-1,x,y)]) 

            rooms[(x,y)]=i_room
            while q:
                x_old,y_old,x_now,y_now = q.popleft()
                
                cand = cango_step(x_now,y_now)
                #print(x_old,y_old,x_now,y_now,time)
                
                if x_now==CH-1 and y_now==CW-1:
                    start_warp = i_room
                if x_now==DH-1 and y_now==DW-1:
                    end_warp = i_room
                
                for x_new,y_new in cand:
                    if not been[x_new][y_new] and S[x_new][y_new]==".":
                        q.append((x_now,y_now,x_new,y_new))
                        been[x_new][y_new]=True
#                        room.append((x_new,y_new))
                        rooms[(x_new,y_new)]=i_room
#            rooms.append(room)

if start_warp==end_warp:
    print(0)
else:
        
    #ワープで行けるほかの部屋をtree入れる
    n_rooms = i_room+1
    tree=[[] for _ in range(n_rooms)]
    
    i_loop=0
    for k,v in rooms.items():
        i_loop+=1
        cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
        for c in cango:
            if c!=v:
                tree[c].append(v)
                tree[v].append(c)
        if i_loop%1000==0:
            for i in range(len(tree)):
                tree[i] = set(tree[i])
        #print(v,cango)

        
    for i in range(len(tree)):
        tree[i] = set(tree[i])
    
    
    q = deque([(-1,start_warp,0)]) #これでもよい
    
    been=[False]*n_rooms
    been[start_warp]=True
    reach=False
    while q:
        parent,x,time = q.popleft()
        if x==end_warp:
            reach=True
            break
        
        for y in tree[x]:
            if not been[y]:
                q.append((x,y,time+1))#子ノードを追加
                been[y]=True
        #print(parent,x,q,time)
    if reach:
        print(time)
    else:
        print(-1)

Buggy submission (verdict: Runtime Error):
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def cango_step(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
def cango_warp(x,y):
    cand = [(i,j) 
            for i in range(x-2,x+3) for j in range(y-2,y+3) 
            if 0<=i and i<=H-1 and 0<=j and j<=W-1]
    return cand

been = [[False]*W for _ in range(H)]
rooms=dict()
i_room=-1
for x in range(H):
    for y in range(W):
        if S[x][y]=="." and not been[x][y]:
            i_room+=1
            been[x][y]=True
            q = deque([(-1,-1,x,y)]) 

            rooms[(x,y)]=i_room
            while q:
                x_old,y_old,x_now,y_now = q.popleft()
                
                cand = cango_step(x_now,y_now)
                #print(x_old,y_old,x_now,y_now,time)
                
                if x_now==CH-1 and y_now==CW-1:
                    start_warp = i_room
                if x_now==DH-1 and y_now==DW-1:
                    end_warp = i_room
                
                for x_new,y_new in cand:
                    if not been[x_new][y_new] and S[x_new][y_new]==".":
                        q.append((x_now,y_now,x_new,y_new))
                        been[x_new][y_new]=True
#                        room.append((x_new,y_new))
                        rooms[(x_new,y_new)]=i_room
#            rooms.append(room)

if start_warp==end_warp:
    print(0)
else:
        
    #ワープで行けるほかの部屋をtree入れる
    n_rooms = i_room+1
    tree=[[] for _ in range(n_rooms)]
    
    i_loop=0
    for k,v in rooms.items():
        i_loop+=1
        cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
        for c in cango:
            if c!=v:
                tree[c].append(v)
                tree[v].append(c)
        if i_loop%1000==0:
                for i in range(len(tree)):
                    tree[i] = set(tree[i])
        #print(v,cango)

        
    for i in range(len(tree)):
        tree[i] = set(tree[i])
    
    
    q = deque([(-1,start_warp,0)]) #これでもよい
    
    been=[False]*n_rooms
    been[start_warp]=True
    reach=False
    while q:
        parent,x,time = q.popleft()
        if x==end_warp:
            reach=True
            break
        
        for y in tree[x]:
            if not been[y]:
                q.append((x,y,time+1))#子ノードを追加
                been[y]=True
        #print(parent,x,q,time)
    if reach:
        print(time)
    else:
        print(-1)