Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in P:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
            que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in P:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
            que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != '#':
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input()) for _ in range(h)]

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NX, NY in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PX, PY in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NX, NY in N:
        nx = x + NX
        ny = y + NY
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for PX, PY in P:
        px = x + PX
        py = y + PY
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([[0, ch, cw]])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft([count, ny, nx])
    for qx, qy in zip(PX, PY):
        px = x + qx
        py = y + qy
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append([count + 1, py, px])

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for qx, qy in zip(PX, PY):
        px = x + qx
        py = y + qy
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

def input(): return sys.stdin.readline().rstrip()

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])