Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    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())
    G = [input() for _ in range(H)]

    INF = 10 ** 12
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0
    # q.appendleft 使用
    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny = dy + sy
            nx = dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.appendleft((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8 = dy8 + sy
            nx8 = dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.appendleft((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque


def resolve():
    drc4 = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    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())
    G = [input() for _ in range(H)]

    INF = 10 ** 12
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny = dy + sy
            nx = dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8 = dy8 + sy
            nx8 = dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    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())
    G = [input() for _ in range(H)]

    INF = 10 ** 12
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, inp().split())
    sy, sx = map(lambda x: int(x) - 1, inp().split())
    gy, gx = map(lambda x: int(x) - 1, inp().split())
    G = [inpS() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()


Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Runtime Error):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, inp().split())
    gy, gx = map(lambda x: int(x) - 1, inp().split())
    G = [inpS() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    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())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Runtime Error):

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    reoslve()


Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    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())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append((sy, sx, 0))
        ans[sy][sx] = 0

        while q:
            sy, sx, cost = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                    ans[ny][nx] = cost
                    q.append((ny, nx, cost))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                    ans[ny8][nx8] = cost + 1
                    q.append((ny8, nx8, cost + 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())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append((sy, sx, 0))
        ans[sy][sx] = 0

        while q:
            sy, sx, cost = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W:
                    if G[ny][nx] == "." and ans[ny][nx] > cost:
                        ans[ny][nx] = cost
                        q.append((ny, nx, cost))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W:
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                        ans[ny8][nx8] = cost + 1
                        q.append((ny8, nx8, cost + 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())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W:
                    if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                        ans[ny][nx] = ans[sy][sx]
                        q.append((ny, nx))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W:
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                        ans[ny8][nx8] = ans[sy][sx] + 1
                        q.append((ny8, nx8))

    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())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            # if sy == gy and sx == gx:
            #     return print(ans[gy][gx])
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                # if G[ny][nx] == "@" or ans[ny][nx] != INF:
                #     if G[ny][nx] != "#":
                #         continue
                if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                    ans[ny][nx] = ans[sy][sx]
                    q.append((ny, nx))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 1 <= ny8 <= H + 1 and 1 <= nx8 <= W + 1:
                    # if G[ny8][nx8] == "#":
                    #     continue
                    # if G[ny8][nx8] == "@" or ans[ny8][nx8] != INF:
                    #     continue
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                        ans[ny8][nx8] = ans[sy][sx] + 1
                        q.append((ny8, nx8))
        # return print(-1)

    H, W = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    G = []
    G.append(["@"] * (W + 2))
    G += [["@"] + list(input()) + ["@"] for _ in range(H)]
    G.append(["@"] * (W + 2))

    INF = 10 ** 7
    ans = [[INF] * (W + 2) for _ in range(H + 2)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            # if sy == gy and sx == gx:
            #     return print(ans[gy][gx])
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                # if G[ny][nx] == "@" or ans[ny][nx] != INF:
                #     if G[ny][nx] != "#":
                #         continue
                if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                    ans[ny][nx] = ans[sy][sx]
                    q.append((ny, nx))

            for dy8 in range(-2, 3):
                for dx8 in range(-2, 3):
                    ny8, nx8 = dy8 + sy, dx8 + sx
                    if 1 <= ny8 <= H + 1 and 1 <= nx8 <= W + 1:
                        # if G[ny8][nx8] == "#":
                        #     continue
                        # if G[ny8][nx8] == "@" or ans[ny8][nx8] != INF:
                        #     continue
                        if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                            ans[ny8][nx8] = ans[sy][sx] + 1
                            q.append((ny8, nx8))
        # return print(-1)

    H, W = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    G = []
    G.append(["@"] * (W + 2))
    G += [["@"] + list(input()) + ["@"] for _ in range(H)]
    G.append(["@"] * (W + 2))

    # visited = [[False] * (W + 2) for _ in range(H+2)]
    INF = 10 ** 7
    ans = [[INF] * (W + 2) for _ in range(H + 2)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Fixed submission:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

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


if __name__ == "__main__":
    resolve()