Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
def label_borderd_4_neighborhoods(image, h, w, neg):
    labeled = [[0] * w for _ in range(h)]
    lut = [0]

    i = 1
    for y in range(1, h-1):
        for x in range(1, w - 1):
            if image[y][x] != neg:
                if labeled[y][x-1] == 0 and labeled[y-1][x] == 0:
                    labeled[y][x] = i
                    lut.append(i)
                    i+=1
                elif labeled[y-1][x] == 0 or labeled[y-1][x] == labeled[y][x-1]:
                    labeled[y][x] = labeled[y][x-1]
                elif labeled[y][x-1] == 0:
                    labeled[y][x] = labeled[y-1][x]
                else:
                    j, k = labeled[y-1][x], labeled[y][x-1]
                    while lut[j] != j:
                        j = lut[j]
                    while lut[k] != k:
                        k = lut[k]
                    l = min(j, k)
                    lut[j], lut[k] = l, l
                    j, k = labeled[y-1][x], labeled[y][x-1]
                    while lut[j] != l:
                        next_j = lut[j]
                        lut[j], j = l, next_j
                    while lut[k] != l:
                        next_k = lut[k]
                        lut[k], k = lut[k], next_k
                    labeled[y][x] = l
    for i in range(len(lut)):
        l = i
        while l != lut[l]:
            l = lut[l]
        j = i
        while j != lut[j]:
            next_j = lut[j]
            lut[j], j = l, next_j
    for y in range(1, h-1):
        for x in range(1, w - 1):
            labeled[y][x] = lut[labeled[y][x]]
    return labeled, len(set(lut)) - 1

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x)+1, input().split())
gy, gx = map(lambda x:int(x)+1, input().split())
grid = [['#'] * (w + 4) for _ in range(2)]
for y in range(h):
    grid.append(['#', '#'] + [c for c in input()] + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

labeled, label_n = label_borderd_4_neighborhoods(grid, h + 4, w + 4, '#')

s = labeled[sy][sx]
g = labeled[gy][gx]
if s == g:
    print(0)
    quit()

q = [(0, sy, sx)]
visited = set()
ans = 0
while q:
    n, y, x = heappop(q)
    if (y, x) in visited:
        continue
    if labeled[y][x] == g:
        ans = n
        q.append((0, 0, 0)) # dummy
        break
    visited.add((y, x))
    for dy in range(-2, 3):
        yy = y + dy 
        for dx in range(-2, 3):
            xx = x + dx
            if labeled[yy][xx] != 0 and not (yy, xx) in visited:
                if abs(dx) + abs(dy) == 1:
                    heappush(q, (n, yy, xx))
                elif labeled[yy][xx] != labeled[y][x]:
                    heappush(q, (n+1, yy, xx))
print(ans if q else -1)




Fixed submission:
h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) + 1, input().split()) 
gy, gx = map(lambda x:int(x) + 1, input().split()) 
grid = [['#'] * (w + 4) for _ in range(2)]
for _ in range(h):
    grid.append(['#', '#'] + list(input()) + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

stack = [(sy, sx)]

move = [(-1, 0), (1, 0), (0, 1), (0, -1)]

visited = set()
ans = 0
while stack:
    edge = set()
    while stack:
        y, x = stack.pop()
        visited.add((y, x))
        if gy == y and gx == x:
            print(ans)
            quit()
        for my, mx in move:
            if (y+my, x+mx) in visited:
                continue
            if grid[y+my][x+mx] == '.':
                stack.append((y+my, x+mx))
            else:
                edge.add((y, x))
    ans += 1
    next_points = set()
    for y, x in edge:
        for dy in range(-2, 3):
            yy = y + dy
            for dx in range(-2, 3):
                xx = x + dx
                if grid[yy][xx] == '.' and not (yy, xx) in visited and not (yy, xx) in next_points:
                    next_points.add((yy, xx))
    stack = list(next_points)
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
h, w = map(int, input().split())
sy, sx = map(lambda x : int(x) + 1, input().split())
gy, gx = map(lambda x : int(x) + 1, input().split())
grid = [['#'] * (w + 4) for _ in range(2)]
for y in range(h):
    grid.append(['#', '#'] + [c for c in input()] + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

q = [(0, sy, sx)]
visited = set()

ans = 0
while q:
    n, y, x = heappop(q)
    if (y, x) in visited:
        continue
    if y == gy and x == gx:
        ans = n
        q.append((0, 0, 0)) # dummy
        break
    visited.add((y, x))
    for dy in range(-2, 3):
        yy = y + dy 
        for dx in range(-2, 3):
            xx = x + dx
            if grid[yy][xx] == '.' and (not (yy, xx) in visited):
                if abs(dx) + abs(dy) == 1:
                    heappush(q, (n, yy, xx))
                else:
                    heappush(q, (n+1, yy, xx))

print(ans if q else -1)




Fixed submission:
h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) + 1, input().split()) 
gy, gx = map(lambda x:int(x) + 1, input().split()) 
grid = [['#'] * (w + 4) for _ in range(2)]
for _ in range(h):
    grid.append(['#', '#'] + list(input()) + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

stack = [(sy, sx)]

move = [(-1, 0), (1, 0), (0, 1), (0, -1)]

visited = set()
ans = 0
while stack:
    edge = set()
    while stack:
        y, x = stack.pop()
        visited.add((y, x))
        if gy == y and gx == x:
            print(ans)
            quit()
        for my, mx in move:
            if (y+my, x+mx) in visited:
                continue
            if grid[y+my][x+mx] == '.':
                stack.append((y+my, x+mx))
            else:
                edge.add((y, x))
    ans += 1
    next_points = set()
    for y, x in edge:
        for dy in range(-2, 3):
            yy = y + dy
            for dx in range(-2, 3):
                xx = x + dx
                if grid[yy][xx] == '.' and not (yy, xx) in visited and not (yy, xx) in next_points:
                    next_points.add((yy, xx))
    stack = list(next_points)
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
def label_borderd_4_neighborhoods(image, h, w, neg):
    labeled = [[0] * w for _ in range(h)]
    lut = [0]

    i = 1
    for y in range(1, h-1):
        for x in range(1, w - 1):
            if image[y][x] != neg:
                if labeled[y][x-1] == 0 and labeled[y-1][x] == 0:
                    labeled[y][x] = i
                    lut.append(i)
                    i+=1
                elif labeled[y-1][x] == 0 or labeled[y-1][x] == labeled[y][x-1]:
                    labeled[y][x] = labeled[y][x-1]
                elif labeled[y][x-1] == 0:
                    labeled[y][x] = labeled[y-1][x]
                else:
                    j, k = labeled[y-1][x], labeled[y][x-1]
                    while lut[j] != j:
                        j = lut[j]
                    while lut[k] != k:
                        k = lut[k]
                    l = min(j, k)
                    lut[j], lut[k] = l, l
                    j, k = labeled[y-1][x], labeled[y][x-1]
                    while lut[j] != l:
                        next_j = lut[j]
                        lut[j], j = l, next_j
                    while lut[k] != l:
                        next_k = lut[k]
                        lut[k], k = lut[k], next_k
                    labeled[y][x] = l
    for i in range(len(lut)):
        l = i
        while l != lut[l]:
            l = lut[l]
        j = i
        while j != lut[j]:
            next_j = lut[j]
            lut[j], j = l, next_j
    for y in range(1, h-1):
        for x in range(1, w - 1):
            labeled[y][x] = lut[labeled[y][x]]
    return labeled, len(set(lut)) - 1

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x)+1, input().split())
gy, gx = map(lambda x:int(x)+1, input().split())
grid = [['#'] * (w + 4) for _ in range(2)]
for y in range(h):
    grid.append(['#', '#'] + [c for c in input()] + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

labeled, label_n = label_borderd_4_neighborhoods(grid, h + 4, w + 4, '#')

s = labeled[sy][sx]
g = labeled[gy][gx]
if s == g:
    print(0)
    quit()

q = [(0, sy, sx)]
visited = set()
ans = 0
while q:
    n, y, x = heappop(q)
    if (y, x) in visited:
        continue
    if labeled[y][x] == g:
        ans = n
        q.append((0, 0, 0)) # dummy
        break
    visited.add((y, x))
    for dy in range(-2, 3):
        yy = y + dy 
        for dx in range(-2, 3):
            xx = x + dx
            if labeled[yy][xx] != 0 and not (yy, xx) in visited:
                if abs(dx) + abs(dy) == 1:
                    heappush(q, (n, yy, xx))
                elif labeled[yy][xx] != labeled[y][x]:
                    heappush(q, (n+1, yy, xx))
print(ans if q else -1)




Fixed submission:
h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) + 1, input().split()) 
gy, gx = map(lambda x:int(x) + 1, input().split()) 
grid = [['#'] * (w + 4) for _ in range(2)]
for _ in range(h):
    grid.append(['#', '#'] + list(input()) + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

stack = [(sy, sx)]

move = [(-1, 0), (1, 0), (0, 1), (0, -1)]

visited = set()
ans = 0
while stack:
    edge = set()
    while stack:
        y, x = stack.pop()
        visited.add((y, x))
        if gy == y and gx == x:
            print(ans)
            quit()
        for my, mx in move:
            if (y+my, x+mx) in visited:
                continue
            if grid[y+my][x+mx] == '.':
                stack.append((y+my, x+mx))
            else:
                edge.add((y, x))
    ans += 1
    next_points = set()
    for y, x in edge:
        for dy in range(-2, 3):
            yy = y + dy
            for dx in range(-2, 3):
                xx = x + dx
                if grid[yy][xx] == '.' and not (yy, xx) in visited and not (yy, xx) in next_points:
                    next_points.add((yy, xx))
    stack = list(next_points)
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
h, w = map(int, input().split())
sy, sx = map(lambda x : int(x) + 1, input().split())
gy, gx = map(lambda x : int(x) + 1, input().split())
grid = [['#'] * (w + 4) for _ in range(2)]
for y in range(h):
    grid.append(['#', '#'] + [c for c in input()] + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

q = [(0, sy, sx)]
visited = set()

ans = 0
while q:
    n, y, x = heappop(q)
    if (y, x) in visited:
        continue
    if y == gy and x == gx:
        ans = n
        q.append((0, 0, 0)) # dummy
        break
    visited.add((y, x))
    for dy in range(-2, 3):
        yy = y + dy 
        for dx in range(-2, 3):
            xx = x + dx
            if grid[yy][xx] == '.' and (not (yy, xx) in visited):
                if abs(dx) + abs(dy) == 1:
                    heappush(q, (n, yy, xx))
                else:
                    heappush(q, (n+1, yy, xx))

print(ans if q else -1)




Fixed submission:
h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) + 1, input().split()) 
gy, gx = map(lambda x:int(x) + 1, input().split()) 
grid = [['#'] * (w + 4) for _ in range(2)]
for _ in range(h):
    grid.append(['#', '#'] + list(input()) + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

stack = [(sy, sx)]

move = [(-1, 0), (1, 0), (0, 1), (0, -1)]

visited = set()
ans = 0
while stack:
    edge = set()
    while stack:
        y, x = stack.pop()
        visited.add((y, x))
        if gy == y and gx == x:
            print(ans)
            quit()
        for my, mx in move:
            if (y+my, x+mx) in visited:
                continue
            if grid[y+my][x+mx] == '.':
                stack.append((y+my, x+mx))
            else:
                edge.add((y, x))
    ans += 1
    next_points = set()
    for y, x in edge:
        for dy in range(-2, 3):
            yy = y + dy
            for dx in range(-2, 3):
                xx = x + dx
                if grid[yy][xx] == '.' and not (yy, xx) in visited and not (yy, xx) in next_points:
                    next_points.add((yy, xx))
    stack = list(next_points)
print(-1)