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

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)


Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)

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

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])

while queue:
    i, j = queue.popleft()
    adj = []
    if i > 0 and S[i - 1][j] == '.':
        adj.append((i-1, j))
    if j > 0 and S[i][j - 1] == '.':
        adj.append((i, j - 1))
    if i < h-1 and S[i + 1][j] == '.':
        adj.append((i+1, j))
    if j < w-1 and S[i][j+1] == '.':
        adj.append((i, j+1))
    for u, v in adj:
        if distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u,v))

    warp = product(range(max(i-2, 0), min(i+3, h)),
                   range(max(j-2, 0), min(j+3, w)))
    for x, y in warp:
        if (x,y) != (i,j) and (x,y) not in adj and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x,y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)



Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)

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

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]

reached = [[False for _ in range(w)] for _ in range(h)]
distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])

while queue:
    i, j = queue.popleft()
    reached[i][j] = True
    adj = []
    if i > 0 and S[i - 1][j] == '.':
        adj.append((i-1, j))
    if j > 0 and S[i][j - 1] == '.':
        adj.append((i, j - 1))
    if i < h-1 and S[i + 1][j] == '.':
        adj.append((i+1, j))
    if j < w-1 and S[i][j+1] == '.':
        adj.append((i, j+1))
    for u, v in adj:
        if not reached[u][v]:
            distance[u][v] = min(distance[i][j],  distance[u][v])
            queue.appendleft((u,v))

    warp = product(range(max(i-2, 0), min(i+3, h)),
                   range(max(j-2, 0), min(j+3, w)))
    for x, y in warp:
        if (x,y) != (i,j) and (x,y) not in adj and S[x][y] == '.' and not reached[x][y]:
            distance[x][y] = min(distance[i][j] + 1,  distance[x][y])
            queue.append((x,y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)



Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)

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

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
roads = set()
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            roads.add((i, j))

reached = {k: False for k in roads}
distance = {v: math.inf for v in roads}
distance[c] = 0
reached = {k: False for k in roads}
queue = deque([c])

while queue:
    u = queue.popleft()
    reached[u] = True
    i, j = u
    adj = []
    if i > 0 and S[i - 1, j] == '.':
        adj.append((i-1, j))
    if j > 0 and S[i, j - 1] == '.':
        adj.append((i, j - 1))
    if i < h-1 and S[i + 1, j] == '.':
        adj.append((i+1, j))
    if j < w-1 and S[i, j+1] == '.':
        adj.append((i, j+1))
    for v in adj:
        if not reached[v]:
            distance[v] = distance[u]
            queue.appendleft(v)

    warp = product(range(max(i-2, 0), min(i+3, h)),
                   range(max(j-2, 0), min(j+3, w)))
    for wa in warp:
        if wa != u and wa not in adj and S[wa] == '.' and not reached[wa]:
            distance[wa] = distance[u] + 1
            queue.append(wa)

print(distance[d] if distance[d] != math.inf else -1)



Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)

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

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
roads = set()
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            roads.add((i, j))

index = 0
section = {}
reached = {k: False for k in roads}

for p in roads:
    if reached[p]:
        continue
    else:
        reached[p] = True
        stack = [p]
        section[p] = index
        while stack:
            v = stack.pop()
            i, j = v
            adj = []
            if i > 0 and S[i - 1, j] == '.':
                adj.append((i-1, j))
            if j > 0 and S[i, j - 1] == '.':
                adj.append((i, j - 1))
            if i < h-1 and S[i + 1, j] == '.':
                adj.append((i+1, j))
            if j < w-1 and S[i, j+1] == '.':
                adj.append((i, j+1))
            for u in adj:
                if not reached[u]:
                    reached[u] = True
                    stack.append(u)
                    section[u] = index
        index += 1

# print(roads)
# print(section)
if section[c] == section[d]:
    print(0)
    exit(0)

vertex = range(index)
edges = {i: set() for i in vertex}
for i, j in roads:
    head = section[i, j]
    square = product(range(max(i-2, 0), min(i+3, h)),
                     range(max(j-2, 0), min(j+3, w)))
    for m in square:
        if S[m] == '.':
            tail = section[m]
            if tail != head and S[m] == '.':
                edges[tail].add(head)
                edges[head].add(tail)

source = section[c]
target = section[d]
distance = {v: math.inf for v in vertex}
distance[source] = 0
reached_ = {k: False for k in vertex}
reached_[source] = True
queue = deque([source])
while queue:
    u = queue.popleft()
    for v in edges[u]:
        if not reached_[v]:
            reached_[v] = True
            distance[v] = distance[u] + 1
            queue.append(v)

if distance[target] != math.inf:
    print(distance[target])
else:
    print(-1)



Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)

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

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
adjacent = {}
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            adjacent[i, j] = []

for i in range(h):
    for j in range(w):
        if S[i, j] != '.':
            continue
        if i > 0 and S[i - 1, j] == '.' and (i-1, j) not in adjacent[i, j]:
            adjacent[i, j].append((i-1, j))
        if j > 0 and S[i , j - 1] == '.' and (i, j-1) not in adjacent[i, j]:
            adjacent[i, j].append((i, j-1))
        if i < h-1 and S[i + 1, j] == '.' and (i+1, j) not in adjacent[i, j]:
            adjacent[i, j].append((i+1, j))
        if j < w-1 and S[i, j+1] == '.' and (i, j+1) not in adjacent[i, j]:
            adjacent[i, j].append((i, j+1))

index = 0
section = {}
reached = {k: False for k in adjacent}

for p in adjacent:
    if reached[p]:
        continue
    else:
        reached[p] = True
        stack = [p]
        section[p] = index
        while stack:
            v = stack.pop()
            for u in adjacent[v]:
                if not reached[u]:
                    reached[u] = True
                    stack.append(u)
                    section[u] = index
        index += 1

#print(adjacent)
#print(section)
if section[c] == section[d]:
    print(0)
    exit(0)

vertex = range(index)
edges = {i: set() for i in vertex}
for i, j in adjacent:
    head = section[i, j]
    square = product(range(max(i-2, 0), min(i+3, h)), range(max(j-2, 0), min(j+3, w)))
    for m in square:
        if S[m] == '.':
            tail = section[m]
            if tail != head and S[m] == '.':
                edges[tail].add(head)
                edges[head].add(tail)

source = section[c]
target = section[d]
distance = {v: math.inf for v in vertex}
distance[source] = 0
reached_ = {k: False for k in vertex}
reached_[source] = True
queue = deque([source])
while queue:
    u = queue.popleft()
    for v in edges[u]:
        if not reached_[v]:
            reached_[v] = True
            distance[v] = distance[u] + 1
            queue.append(v)

if distance[target] != math.inf:
    print(distance[target])
else:
    print(-1)

Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)

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

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
adjacent = {}
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            adjacent[i, j] = []

for i in range(h):
    for j in range(w):
        if S[i, j] != '.':
            continue
        if i > 0 and S[i - 1, j] == '.' and (i-1, j) not in adjacent[i, j]:
            adjacent[i, j].append((i-1, j))
        if j > 0 and S[i , j - 1] == '.' and (i, j-1) not in adjacent[i, j]:
            adjacent[i, j].append((i, j-1))
        if i < h-1 and S[i + 1, j] == '.' and (i+1, j) not in adjacent[i, j]:
            adjacent[i, j].append((i+1, j))
        if j < w-1 and S[i, j+1] == '.' and (i, j+1) not in adjacent[i, j]:
            adjacent[i, j].append((i, j+1))

index = 0
section = {}
reached = {k: False for k in adjacent}

for p in adjacent:
    if reached[p]:
        continue
    else:
        reached[p] = True
        stack = [p]
        section[p] = index
        while stack:
            v = stack.pop()
            for u in adjacent[v]:
                if not reached[u]:
                    reached[u] = True
                    stack.append(u)
                    section[u] = index
        index += 1

#print(adjacent)
#print(section)
if section[c] == section[d]:
    print(0)
    exit(0)

vertex = range(index)
edges = {i: set() for i in vertex}
for i, j in adjacent:
    head = section[i, j]
    square = product(range(max(i-2, 0), min(i+3, h)), range(max(j-2, 0), min(j+3, w)))
    for m in square:
        if S[m] == '.':
            tail = section[m]
            if tail != head and S[m] == '.':
                edges[tail].add(head)
                edges[head].add(tail)

source = section[c]
target = section[d]
distance = {v: math.inf for v in vertex}
distance[source] = 0
reached_ = {k: False for k in vertex}
reached_[source] = True
queue = deque([source])
while queue:
    u = queue.popleft()
    for v in edges[u]:
        if not reached_[v]:
            reached_[v] = True
            distance[v] = distance[u] + 1
            queue.append(v)

if distance[target] != math.inf:
    print(distance[target])
else:
    print(-1)

Fixed submission:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)