Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dst = [[INF]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for dh in range(-2, 3):
        for dw in range(-2, 3): # [dh,dw]:[-2,-2]~[2,2]
            nh = h + dh; nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] < dst[nh][nw]:
                if dh*dh + dw*dw == 1:
                    dst[nh][nw] = dst[h][w]
                    dq.appendleft((nh, nw))
                elif dh*dh + dw*dw > 1:
                    dst[nh][nw] = dst[h][w] + 1
                    dq.append((nh, nw))

print(-1 if dst[eh][ew]==INF else dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
        for dh in range(-2, 3):
            for dw in range(-2, 3): # [dh,dw]:[-2,-2]~[2,2]
                if dh*dh + dw*dw > 1: dq.append((h + dh, w + dw, d+1))
                else: dq.appendleft((h + dh, w + dw, d))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w]
        elif dst[h][w] < dst[nh][nw]:
            dst[nh][nw] =  dst[h][w]
        else: continue
        dq.append((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dst = [[INF]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] < dst[nh][nw]:
            dst[nh][nw] = dst[h][w]
            dq.appendleft((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
            dq.append((nh, nw))

print(-1 if dst[eh][ew]==INF else dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or dst[h][w] < dst[nh][nw]:
            dst[nh][nw] = dst[h][w]
            dq.appendleft((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = min(dst[nh][nw], dst[h][w] + 1)
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d: continue
        dst[nh][nw] = d
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d: continue
        dst[nh][nw] = d + 1
        dq.appendleft((nh, nw, d + 1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d: continue
        dst[nh][nw] = d
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d + 1: continue
        dst[nh][nw] = d + 1
        dq.appendleft((nh, nw, d + 1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or d < dst[nh][nw]:
            dq.appendleft((nh, nw, d))
            dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1 or d + 1 < dst[nh][nw]:
            dq.append((nh, nw, d + 1))
            dst[nh][nw] = d + 1

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    # if h == eh and w == ew:
    #     dst[h][w] = d
    #     break

    # if dst[h][w] >= 0 or S[h][w] == '#': continue
    # if dst[h][w] >= 0: continue
    # if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d
    # else: continue
    # dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        # if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1 or d < dst[nh][nw]:
            dq.appendleft((nh, nw, d))
            dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1 or d + 1 < dst[nh][nw]:
            dq.append((nh, nw, d + 1))
            dst[nh][nw] = d + 1

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if h == eh and w == ew:
        dst[h][w] = d
        break

    if dst[h][w] >= 0 or S[h][w] == '#': continue
    if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    if dst[h][w] == -1: dst[h][w] = d
    else: dst[h][w] = min(dst[h][w], d)

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] >= 0 or S[h][w] == '#': continue
    if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d
    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh or nw < 0 or W <= nw: continue
        if S[nh][nw] == '#' or 0 <= dst[nh][nw]: continue
        dq.appendleft((nh, nw, d))
    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh or nw < 0 or W <= nw: continue
        if S[nh][nw] == '#' or 0 <= dst[nh][nw]: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d
    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh or nw < 0 or W <= nw: continue
        if S[nh][nw] == '#' or 0 <= dst[nh][nw]: continue
        dq.appendleft((nh, nw, d))
    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh or nw < 0 or W <= nw: continue
        if S[nh][nw] == '#' or 0 <= dst[nh][nw]: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] >= 0 or S[h][w] == '#': continue
    dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    # if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
    if dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and dst[nh][nw] < 0 and S[nh][nw] != '#':
            dq.appendleft((nh, nw, d))
    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if 0 <= nh < H and 0 <= nw < W and dst[nh][nw] < 0 and S[nh][nw] != '#':
            dq.append((nh, nw, d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Buggy python submission (verdict: Time Limit Exceeded):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])


Fixed submission:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])