Problem p02579 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))

    try:
        #ワープ
        for dh,dw in WARP:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
                if kyori+1 < d[(to_h, to_w)]:
                    d[(to_h, to_w)]=kyori+1
                    q.append((kyori+1, to_h, to_w))
    except:
        pass

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori,to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori+1 < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori,to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori+1 < d[(to_h, to_w)]:
                #visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit1=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
visit2=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit1[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)] < d[(to_h, to_w)]:
                visit1[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit2[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)]+1 < d[(to_h, to_w)]:
                visit2[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit1=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
visit2=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit1[(to_h, to_w)]==0:
            visit1[(to_h, to_w)]=1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit2[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)]+1 < d[(to_h, to_w)]:
                visit2[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            visit[(to_h, to_w)]=1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)]+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            visit[(to_h, to_w)]=1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))

print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #print "fro_h, fro_w, q :: ",fro_h, fro_w, q
    #print "fro_h, fro_w, q :: ",fro_h, fro_w
    #print "d :: ",d
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.appendleft((to_h, to_w))
        #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="."  and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.appendleft((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="."  and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.appendleft((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))


q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori,fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            alt=d[(fro_h, fro_w)]+0
            if alt<d[(to_h, to_w)]:
                d[(to_h, to_w)]=alt
                q.appendleft((alt,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            alt=d[(fro_h, fro_w)]+1
            if alt<d[(to_h, to_w)]:
                d[(to_h, to_w)]=alt
                q.append((alt,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit1=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
visit2=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit1[(CH,CW)]=1
visit2[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    if fro_h==DH and fro_w==DW:
        print (kyori)
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit1[(to_h, to_w)]==0:
                    visit1[(to_h, to_w)]=1
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit2[(to_h, to_w)]==0:
                    visit2[(to_h, to_w)]=1
                    q.append((kyori+1, to_h, to_w))

print (-1)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))


q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori,fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            alt=d[(fro_h, fro_w)]+0
            if alt<d[(to_h, to_w)]:
                d[(to_h, to_w)]=alt
                q.appendleft((alt,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            alt=d[(fro_h, fro_w)]+1
            if alt<d[(to_h, to_w)]:
                d[(to_h, to_w)]=alt
                q.append((alt,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    if fro_h==DH and fro_w==DW:
        print kyori
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    visit[(to_h, to_w)]=1
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    visit[(to_h, to_w)]=1
                    q.append((kyori+1, to_h, to_w))

print -1

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
visit[(CH,CW)]=1
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+0
                q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.appendleft((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    if fro_h==DH and fro_w==DW:
        print (kyori)
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    visit[(to_h, to_w)]=1
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    visit[(to_h, to_w)]=1
                    q.append((kyori+1, to_h, to_w))

print (-1)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    if fro_h==DH and fro_w==DW:
        print (kyori)
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    q.append((kyori+1, to_h, to_w))

print (-1)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    if fro_h==DH and fro_w==DW:
        print (kyori)
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    q.append((kyori+1, to_h, to_w))

print (-1)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    if fro_h==DH and fro_w==DW:
        print kyori
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    q.append((kyori+1, to_h, to_w))

print -1

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    if fro_h==DH and fro_w==DW:
        print kyori
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                if visit[(to_h, to_w)]==0:
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                if visit[(to_h, to_w)]==0:
                    q.append((kyori+1, to_h, to_w))

print -1

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from collections import deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

d=defaultdict(lambda: float("inf"))    #(h,w):スタート地点からその点までの距離
visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    if fro_h==DH and fro_w==DW:
        print d[(DH,DW)]
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                alt=d[(fro_h,fro_w)]+0
                if alt<d[(to_h,to_w)] and visit[(to_h, to_w)]==0:
                    d[(to_h, to_w)]=alt
                    q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                alt=d[(fro_h,fro_w)]+1
                if alt<d[(to_h,to_w)] and visit[(to_h, to_w)]==0:
                    d[(to_h, to_w)]=alt
                    q.append((to_h, to_w))

print -1

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from collections import deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

d=defaultdict(lambda: float("inf"))    #(h,w):スタート地点からその点までの距離
visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                alt=d[(fro_h,fro_w)]+0
                if alt<d[(to_h,to_w)] and visit[(to_h, to_w)]==0:
                    d[(to_h, to_w)]=alt
                    q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                alt=d[(fro_h,fro_w)]+1
                if alt<d[(to_h,to_w)] and visit[(to_h, to_w)]==0:
                    d[(to_h, to_w)]=alt
                    q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from collections import deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

d=defaultdict(lambda: float("inf"))    #(h,w):スタート地点からその点までの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                alt=d[(fro_h,fro_w)]+0
                if alt<d[(to_h,to_w)]:
                    d[(to_h, to_w)]=alt
                    q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]==".":
                alt=d[(fro_h,fro_w)]+1
                if alt<d[(to_h,to_w)]:
                    d[(to_h, to_w)]=alt
                    q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(h,w):
    d[(h,w)]=0
    hq=[]
    heappush(hq,(0,h,w))
    while hq:
        cost,fro_h,fro_w=heappop(hq)
        #歩いて移動
        for dh,dw in D:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W:
                if S[to_h][to_w]=="#": continue
                if S[to_h][to_w]==".":
                    alt=d[(fro_h,fro_w)]+0
                    if alt<d[(to_h,to_w)]:
                        d[(to_h,to_w)]=alt
                        heappush(hq, (alt,to_h,to_w))
        #ワープ
        for dh,dw in WARP:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W:
                if S[to_h][to_w]=="#": continue
                if S[to_h][to_w]==".":
                    alt=d[(fro_h,fro_w)]+1
                    if alt<d[(to_h,to_w)]:
                        d[(to_h,to_w)]=alt
                        heappush(hq, (alt,to_h,to_w))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(h,w):
    d[(h,w)]=0
    hq=[]
    heappush(hq,(0,h,w))
    while hq:
        cost,fro_h,fro_w=heappop(hq)
        #歩いて移動
        for dh,dw in D:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W:
                if S[to_h][to_w]==".":
                    alt=d[(fro_h,fro_w)]+0
                    if alt<d[(to_h,to_w)]:
                        d[(to_h,to_w)]=alt
                        heappush(hq, (alt,to_h,to_w))
        #ワープ
        for dh,dw in WARP:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W:
                if S[to_h][to_w]==".":
                    alt=d[(fro_h,fro_w)]+1
                    if alt<d[(to_h,to_w)]:
                        d[(to_h,to_w)]=alt
                        heappush(hq, (alt,to_h,to_w))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            continue
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
    d[(x,y)]=0
    hq=[]
    heappush(hq,(0,x,y))
    while hq:
        cost,fro_x,fro_y=heappop(hq)
        for cost,to_x,to_y in al[(fro_x,fro_y)]:
            if d[(to_x,to_y)]==0: continue
            alt=d[(fro_x,fro_y)]+cost
            if alt<d[(to_x,to_y)]:
                d[(to_x,to_y)]=alt
                heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            continue
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
    d[(x,y)]=0
    hq=[]
    heappush(hq,(0,x,y))
    while hq:
        cost,fro_x,fro_y=heappop(hq)
        for cost,to_x,to_y in al[(fro_x,fro_y)]:
            if d[(to_x,to_y)]==0: continue
            alt=d[(fro_x,fro_y)]+cost
            if alt<d[(to_x,to_y)]:
                d[(to_x,to_y)]=alt
                heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            continue
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ list(sys.stdin.readline().strip()) for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]