Buggy python submission (verdict: Time Limit Exceeded):
#input
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
s = [input() for _ in range(h)]

#output
from collections import deque

INF = pow(10, 10)
dp = [[INF] * w for _ in range(h)]

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

q = deque([])
q.append((c_h-1, c_w-1))
dp[c_h-1][c_w-1] = 0

while q:
    x, y = q.popleft()

    for dx, dy in trans_a:
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
            q.appendleft((nx, ny))#ここを変更
            dp[nx][ny] = dp[x][y]#ここを変更

    for dx, dy in trans_b:
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
            q.append((nx, ny))
            dp[nx][ny] = dp[x][y] + 1

answer = dp[d_h-1][d_w-1]

# %%
if answer == INF:
    print(-1)
else:
    print(answer)

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#input
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
s = [input() for _ in range(h)]

#output
from collections import deque

INF = pow(10, 10)
dp = [[INF] * w for _ in range(h)]

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

q = deque([])
q.append((c_h-1, c_w-1))
dp[c_h-1][c_w-1] = 0

while q:
    x, y = q.popleft()

    for dx, dy in trans_a:
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
            q.appendleft((nx, ny))#ここを変更
            dp[nx][ny] = dp[x][y]#ここを変更

    for dxb, dyb in trans_b:
        nx2, ny2 = x + dxb, y + dyb
        if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
            q.append((nx2, ny2))
            dp[nx2][ny2] = dp[x][y] + 1

answer = dp[d_h-1][d_w-1]

# %%
if answer == INF:
    print(-1)
else:
    print(answer)

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = [input() for _ in range(h)]

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

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

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1][c_w-1] = 0

    while q:
        x, y = q.popleft()

        for dx, dy in trans_a:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx][ny] = dp[x][y]#ここを変更

        for dxb, dyb in trans_b:
            nx2, ny2 = x + dxb, y + dyb
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                q.append((nx2, ny2))
                dp[nx2][ny2] = dp[x][y] + 1

    answer = dp[d_h-1][d_w-1]

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = [input() for _ in range(h)]

    #output
    from collections import deque
    import numpy as np

    INF = pow(10, 10)
    dp = np.full((h, w), INF)
    #dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1, c_w-1] = 0

    while q:
        x, y = q.popleft()

        if x == d_h-1 and y == d_w-1:
            break

        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx, ny] > dp[x, y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx, ny] = dp[x, y]#ここを変更

        for j in range(0, 20):
            nx2, ny2 = x + dxb[j], y + dyb[j]
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2, ny2] > dp[x, y]:
                q.append((nx2, ny2))
                dp[nx2, ny2] = dp[x, y] + 1

    """def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()"""

    answer = dp[d_h-1, d_w-1]

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = [input() for _ in range(h)]

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1][c_w-1] = 0

    while q:
        x, y = q.popleft()

        if x == d_h-1 and y == d_w-1:
            break

        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx][ny] = dp[x][y]#ここを変更

        for j in range(0, 20):
            nx2, ny2 = x + dxb[j], y + dyb[j]
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                q.append((nx2, ny2))
                dp[nx2][ny2] = dp[x][y] + 1

    """def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()"""

    answer = dp[d_h-1][d_w-1] if dp[d_h-1][d_w-1] < INF else "-1"

    # %%
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = [input() for _ in range(h)]

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1][c_w-1] = 0

    while q:
        x, y = q.popleft()

        if x == d_h-1 and y == d_w-1:
            break

        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx][ny] = dp[x][y]#ここを変更

        for j in range(0, 20):
            nx2, ny2 = x + dxb[j], y + dyb[j]
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                q.append((nx2, ny2))
                dp[nx2][ny2] = dp[x][y] + 1

    """def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()"""

    answer = dp[d_h-1][d_w-1]

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1][c_w-1] = 0

    while q:
        x, y = q.popleft()

        if x == d_h-1 and y == d_w-1:
            break

        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx][ny] = dp[x][y]#ここを変更

        for j in range(0, 20):
            nx2, ny2 = x + dxb[j], y + dyb[j]
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                q.append((nx2, ny2))
                dp[nx2][ny2] = dp[x][y] + 1

    """def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()"""

    answer = dp[d_h-1][d_w-1]

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1][c_w-1] = 0

    while len(q):
        x, y = q.popleft()

        if x == d_h-1 and y == d_w-1:
            break

        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx][ny] = dp[x][y]#ここを変更

        for j in range(0, 20):
            nx2, ny2 = x + dxb[j], y + dyb[j]
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                q.append((nx2, ny2))
                dp[nx2][ny2] = dp[x][y] + 1

    """def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()"""

    answer = dp[d_h-1][d_w-1]

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s)

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s) if clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s) < INF else "-1" 
    # %%
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s) if clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s) < INF else "-1" 
    # %%
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s)
    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s)
    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Fixed submission:
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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)