Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys
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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

def input():
    return sys.stdin.readline()[:-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] <= reached[h][w]:
                continue
            reached[nh][nw] = reached[h][w]
            heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] <= reached[h][w] + cost:
                    continue
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] <= reached[h][w]:
                continue
            reached[nh][nw] = reached[h][w]
            heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] <= reached[h][w] + cost:
                    continue
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

    

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not 0 <= nh <= H-1 and 0 <= nw <= W-1:
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not 0 <= nh <= H-1 and 0 <= nw <= W-1:
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

    

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if 0 <= nh <= H-1 and 0 <= nw <= W-1 and maze[nh][nw] != "#" and reached[nh][nw] > d:
            reached[nh][nw] = d
            l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if 0 <= nh <= H-1 and 0 <= nw <= W-1 and maze[nh][nw] != "#" and reached[nh][nw] > d:
                reached[nh][nw] = d + 1
                l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

    

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if 0 <= nh <= H-1 and 0 <= nw <= W-1 and maze[nh][nw] != "#" and reached[nh][nw] > d:
            reached[nh][nw] = d
            l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if 0 <= nh <= H-1 and 0 <= nw <= W-1 and maze[nh][nw] != "#" and reached[nh][nw] > d:
                reached[nh][nw] = d + 1
                l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

    

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
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

maze = []
for i in range(H):
    maze.append(list(input()))

cnt = 0
reached = [[False]*W for _ in range(H)]
def bfs(sh, sw):
    global cnt
    d = deque()
    #reached[Ch][Cw] = True
    d.append((sh, sw))
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            cnt += 1
                            bfs(i, j)


bfs(Ch, Cw)
print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
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

maze = []
for i in range(H):
    maze.append(list(input()))

cnt = 0

def bfs():
    global cnt
    reached = [[False]*W for _ in range(H)]

    d = deque()
    d.append((Ch, Cw))
    #reached[Ch][Cw] = True
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            d.append((i, j))
        if d:
            cnt += 1

bfs()
print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
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

maze = []
for i in range(H):
    maze.append(list(input()))

cnt = 0

def bfs():
    global cnt
    reached = [[False for _ in range(W)] for _ in range(H)]

    d = deque()
    d.append((Ch, Cw))
    #reached[Ch][Cw] = True
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            d.append((i, j))
        if d:
            cnt += 1

bfs()
print(-1)

Fixed submission:
from collections import deque

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

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)