Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze.append(readline().rstrip().decode('utf-8'))
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(3):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            #h*W+w,(h+i-2)*W+w+j-2
                            fr,go = h*W+w,(h+i-2)*W+w+j-2
                            if abs(i-2)+abs(j-2) <= 1:
                                g[fr].append((0,go))
                                g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])



Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze.append(readline().rstrip().decode('utf-8'))
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            #h*W+w,(h+i-2)*W+w+j-2
                            fr,go = h*W+w,(h+i-2)*W+w+j-2
                            if abs(i-2)+abs(j-2) <= 1:
                                g[fr].append((0,go))
                                #g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                #g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])



Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            #h*W+w,(h+i-2)*W+w+j-2
                            fr,go = h*W+w,(h+i-2)*W+w+j-2
                            if abs(i-2)+abs(j-2) <= 1:
                                g[fr].append((0,go))
                                #g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                #g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])



Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            if abs(i-2)+abs(j-2) <= 1:
                                #h*W+w,(h+i-2)*W+w+j-2
                                fr,go = h*W+w,(h+i-2)*W+w+j-2
                                g[fr].append((0,go))
                                #g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                #g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])



Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(2,5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            if abs(i-2)+abs(j-2) <= 1:
                                #h*W+w,(h+i-2)*W+w+j-2
                                g[h*W+w].append((0,(h+i-2)*W+w+j-2))
                                g[(h+i-2)*W+w+j-2].append((0,h*W+w))
                            else:
                                g[h*W+w].append((1,(h+i-2)*W+w+j-2))
                                g[(h+i-2)*W+w+j-2].append((1,h*W+w))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])



Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            if abs(i-2)+abs(j-2) <= 1:
                                #h*W+w,(h+i-2)*W+w+j-2
                                g[h*W+w].append((0,(h+i-2)*W+w+j-2))
                                g[(h+i-2)*W+w+j-2].append((0,h*W+w))
                            else:
                                g[h*W+w].append((1,(h+i-2)*W+w+j-2))
                                g[(h+i-2)*W+w+j-2].append((1,h*W+w))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])



Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[200000]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)


Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)


Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)


Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
deq = deque([(0,sh,sw)])
visited[sh][sw] = 0
ans = 10**9
while deq:
    rp,h,w = deq.pop()
    if h == gh and w == gw:
        ans = min(ans,rp)
        continue
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                deq.append((rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            deq.append((rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(ans if ans != 10**9 else -1)

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
import time
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
t1 = time.time()
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
    if time.time()-t1 >= 1.90:
        print(-1)
        exit()

print(-1)

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0

while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1

print(-1)

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**18]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0

while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
                    


print(-1)
    




Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    res = [-1]*W
    s = readline().rstrip().decode('utf-8')
    for i in range(W):
        if s[i] == ".":
            res[i] = 0
    maze.append(res)
    #maze += [list(readline().rstrip().decode().replace(".",0).replace("#",-1))]
    

ct = 1
for h in range(H):
    for w in range(W):
        if maze[h][w] == 0:
            y,x = h,w
            maze[y][x] = ct
            stack = deque([[y,x]])
            while stack:
                i,j = stack.pop()
                for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
                    if not 0 <= i + ni < H or not 0 <= j + nj < W:
                        continue
                    if maze[i+ni][j+nj] == 0:
                        maze[i+ni][j+nj] = ct
                        stack.append([i+ni,j+nj])
            ct += 1

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze[h][w] != -1:
                for i,j in [(-1,-2),(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,2),(0,2)]:
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze[h+i][w+j] != -1 and \
                            not g2[maze[h][w]][maze[h+i][w+j]]:
                            g[maze[h][w]].append((1,maze[h+i][w+j]))
                            g[maze[h+i][w+j]].append((1,maze[h][w]))
                            g2[maze[h][w]][maze[h+i][w+j]] = 1
                            g2[maze[h+i][w+j]][maze[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze[sh-1][sw-1]
goal = maze[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    res = [-1]*W
    s = readline().rstrip().decode('utf-8')
    for i in range(W):
        if s[i] == ".":
            res[i] = 0
    maze.append(res)
    #maze += [list(readline().rstrip().decode().replace(".",0).replace("#",-1))]
    

ct = 1
for h in range(H):
    for w in range(W):
        if maze[h][w] == 0:
            y,x = h,w
            maze[y][x] = ct
            stack = deque([[y,x]])
            while stack:
                i,j = stack.pop()
                for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
                    if not 0 <= i + ni < H or not 0 <= j + nj < W:
                        continue
                    if maze[i+ni][j+nj] == 0:
                        maze[i+ni][j+nj] = ct
                        stack.append([i+ni,j+nj])
            ct += 1

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze[h][w] != -1:
                for i in range(3):
                    for j in range(-2,3):
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze[h+i][w+j] != -1 and \
                            not g2[maze[h][w]][maze[h+i][w+j]]:
                            g[maze[h][w]].append((1,maze[h+i][w+j]))
                            g[maze[h+i][w+j]].append((1,maze[h][w]))
                            g2[maze[h][w]][maze[h+i][w+j]] = 1
                            g2[maze[h+i][w+j]][maze[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze[sh-1][sw-1]
goal = maze[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

maze2 = [[-1]*W for _ in range(H)]

ct = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == "." and maze2[h][w] == -1:
            y,x = h,w
            maze2[y][x] = ct
            stack = deque([[y,x]])
            while stack:
                i,j = stack.pop()
                for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
                    if not 0 <= i + ni < H or not 0 <= j + nj < W:
                        continue
                    if maze[i+ni][j+nj] == "." and maze2[i+ni][j+nj] == -1:
                        maze2[i+ni][j+nj] = ct
                        stack.append([i+ni,j+nj])
            ct += 1

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze2[h][w] != -1:
                for i in range(3):
                    for j in range(-2,3):
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze2[h+i][w+j] != -1 and \
                            not g2[maze2[h][w]][maze2[h+i][w+j]]:
                            g[maze2[h][w]].append((1,maze2[h+i][w+j]))
                            g[maze2[h+i][w+j]].append((1,maze2[h][w]))
                            g2[maze2[h][w]][maze2[h+i][w+j]] = 1
                            g2[maze2[h+i][w+j]][maze2[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze2[sh-1][sw-1]
goal = maze2[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

maze2 = [[-1]*W for _ in range(H)]

def mizutamari(maze,maze2,y,x,ct):
    maze2[y][x] = ct
    stack = deque([[y,x]])
    while stack:
        i,j = stack.pop()
        for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not 0 <= i + ni < H or not 0 <= j + nj < W:
                continue
            if maze[i+ni][j+nj] == "." and maze2[i+ni][j+nj] == -1:
                maze2[i+ni][j+nj] = ct
                stack.append([i+ni,j+nj])
    return maze2

def func(maze,maze2):
    ct = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "." and maze2[h][w] == -1:
                maze2 = mizutamari(maze,maze2,h,w,ct)
                ct += 1
    return maze2,ct

maze2,ct = func(maze,maze2)

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze2[h][w] != -1:
                for i in range(-2,3):
                    for j in range(-2,3):
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze2[h+i][w+j] != -1 and \
                            not g2[maze2[h][w]][maze2[h+i][w+j]]:
                            g[maze2[h][w]].append((1,maze2[h+i][w+j]))
                            g[maze2[h+i][w+j]].append((1,maze2[h][w]))
                            g2[maze2[h][w]][maze2[h+i][w+j]] = 1
                            g2[maze2[h+i][w+j]][maze2[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze2[sh-1][sw-1]
goal = maze2[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])

Fixed submission:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)