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

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)


Fixed submission:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)

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

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)


Fixed submission:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.deque()
q.append([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

cnt = 0
while len(q) != 0:
    cnt += 1
    crntY, crntX = q.popleft()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
            q.append([nextY, nextX])
        else:
            q.appendleft([nextY, nextX])
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Fixed submission:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.Queue()
q.put([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

while q.qsize() != 0:
    crntY, crntX = q.get()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
        q.put([nextY, nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Fixed submission:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.Queue()
q.put([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

while q.qsize() != 0:
    crntY, crntX = q.get()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
        q.put([nextY, nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Fixed submission:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)