Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline
 
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]
 
INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()
 
q = []
heappush(q, (0, Ch*W+Cw))
 
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]
 
while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)
    used.add((i, j))
    if D[i][j] > d:
        D[i][j] = d
    else:
        continue
    if i == Dh and j == Dw:
        break
 
    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i*W+ _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i*W+ _j))
 
ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Fixed submission:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))
    if D[i][j] > d:
        D[i][j] = d
    else:
        continue
    if i == Dh and j == Dw:
        break

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


Fixed submission:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))
    D[i][j] = d
    if i == Dh and j == Dw:
        break

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


Fixed submission:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


Fixed submission:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 0), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 0), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            used.add((i, j))
            if S[_i][_j] == '.':
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


Fixed submission:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)