Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7

def array(*args, initial=0):
    pre = "[" * len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range(" + str(a) + ")]"
    S = pre + "{}".format(initial) + post
    return eval(S)


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = MAP()
    # 空間はINF,壁は-1, →↑←↓
    pond = array(H + 2, W + 2, 4, initial=-1)
    for h in range(1, H + 1):
        for w, c in enumerate(input(), start=1):
            if c == ".":
                for i in range(4):
                    pond[h][w][i] = INF
    q = []
    # 距離(), x, y, 方向
    heappush(q, ((0, 0), x1, y1, 0))
    heappush(q, ((0, 0), x1, y1, 1))
    heappush(q, ((0, 0), x1, y1, 2))
    heappush(q, ((0, 0), x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while q:
        (a0, a1), x, y, d = heappop(q)
        # 順方向へ進む
        nx = x + DX[d]
        ny = y + DY[d]
        # print((a0, a1), x, y, d, nx, ny)
        if pond[nx][ny][0] == -1:     # 行き止まりなら何もせず
            continue
        if pond[nx][ny][(d + 1) % 4] > a0 + 1:
            pond[nx][ny][(d + 1) % 4] = a0 + 1
            heappush(q, ((a0 + 1, 0), nx, ny, (d + 1) % 4))
        if pond[nx][ny][(d - 1) % 4] > a0 + 1:
            pond[nx][ny][(d - 1) % 4] = a0 + 1
            heappush(q, ((a0 + 1, 0), nx, ny, (d - 1) % 4))
        if pond[nx][ny][d] >= a0 + 1:
            pond[nx][ny][d] = a0 + 1
            if a1 + 1 < K:
                heappush(q, ((a0, a1 + 1), nx, ny, d))
            else:
                heappush(q, ((a0 + 1, 0), nx, ny, d))
        if (nx, ny) == (x2, y2):
            print(a0 + 1)
            return
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

@profile
def main():
    from heapq import heappush, heappop, heapify
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    # 0123: 上下左右
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        new_stack = []
        while stack:
            curr, x, y, d = heappop(stack)
            dx, dy = DX[d], DY[d]
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * dx, y + k * dy
                if c[xx][yy] == 0:
                    b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d - 1) % 4))
                    b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d + 1) % 4))
                    c[xx][yy] = a
                elif c[xx][yy] != a:
                    flag = False
                    break
            if flag:
                heappush(new_stack, (a, xx, yy, d))
            if c[x2][y2] > 0:
                print(c[x2][y2], flush=True)
                exit(0)
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    # 0123: 上下左右
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        curr, x, y, d = heappop(stack)
        flag = True
        a = curr + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                if b == 0 or b == a + 1:
                    heappush(stack, (a, xx, yy, (d - 1) % 4))
                b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                if b == 0 or b == a + 1:
                    heappush(stack, (a, xx, yy, (d + 1) % 4))
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            heappush(stack, (a, xx, yy, d))
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    # 0123: 上下左右
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        curr, x, y, d = heappop(stack)
        flag = True
        a = curr + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                if b == 0 or b == a + 1:
                    heappush(stack, (a, xx, yy, (d - 1) % 4))
                b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                if b == 0 or b == a + 1:
                    heappush(stack, (a, xx, yy, (d + 1) % 4))
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            heappush(stack, (a, xx, yy, d))
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = [((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
             ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while head < len(stack):
        b = stack[head]
        head += 1
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] != 0 and c[xx][yy] != a:
                flag = False
                break
            stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
            stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
            c[xx][yy] = a
        if flag:
            stack.append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**6 + 10


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[0] + [0 if c == "." else -1 for c in input()] + [0]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0
    updated = []

    # 0123: 上下左右
    stack = [((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
             ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            b = stack[head]
            d = b % 4
            x, y = divmod(b >> 2, KETA)
            head += 1
            flag = True
            a = c[x][y] + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if not (c[xx][yy] == 0 or c[xx][yy] == a):
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                new_stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                updated.append((a, xx, yy))
            if flag:
                new_stack.append(((xx * KETA + yy) << 2) + d)
        stack = new_stack
        for a, xx, yy in updated:
            c[xx][yy] = a
        update = []

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [["@"] + [c for c in input()] + ["@"] for i in range(H)]
    c = [["@"] * (W + 2)] + c + [["@"] * (W + 2)]
    c[x1][y1] = 0
    updated = []

    # 0123: 上下左右
    stack = [((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
             ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            b = stack[head]
            d = b % 4
            x, y = divmod(b >> 2, KETA)
            head += 1
            flag = True
            a = c[x][y] + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if c[xx][yy] != ".":
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                new_stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                updated.append((a, xx, yy))
            if flag:
                new_stack.append(((xx * KETA + yy) << 2) + d)
        stack = new_stack
        for a, xx, yy in updated:
            c[xx][yy] = a
        update = []

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [["@"] + [c for c in input()] + ["@"] for i in range(H)]
    c = [["@"] * (W + 2)] + c + [["@"] * (W + 2)]
    updated = []

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            curr, x, y, d = stack[head]
            head += 1
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if c[xx][yy] != ".":
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append((a, xx, yy, (d - 1) % 4))
                new_stack.append((a, xx, yy, (d + 1) % 4))
                updated.append((xx, yy))
            if flag:
                new_stack.append((a, xx, yy, d))
        stack = new_stack
        for xx, yy in updated:
            c[xx][yy] = "@"
        update = []

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [["@"] + [c for c in input()] + ["@"] for i in range(H)]
    c = [["@"] * (W + 2)] + c + [["@"] * (W + 2)]
    updated = []

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            curr, x, y, d = stack[head]
            head += 1
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if c[xx][yy] == "@":
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append((a, xx, yy, (d - 1) % 4))
                new_stack.append((a, xx, yy, (d + 1) % 4))
            if flag:
                new_stack.append((a, xx, yy, d))
                updated.append((xx, yy))
        stack = new_stack
        for xx, yy in updated:
            c[xx][yy] = "@"
        update = []

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [["@"] + [c for c in input()] + ["@"] for i in range(H)]
    c = [["@"] * (W + 2)] + c + [["@"] * (W + 2)]
    dd = [cc[:] for cc in c]

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            curr, x, y, d = stack[head]
            head += 1
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if c[xx][yy] == "@":
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append((a, xx, yy, (d - 1) % 4))
                new_stack.append((a, xx, yy, (d + 1) % 4))
            if flag:
                new_stack.append((a, xx, yy, d))
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    while stack:
        curr, x, y, d = heappop(stack)
        # print(curr, x, y, d)
        if d == 0:
            dx, dy = 1, 0
        elif d == 1:
            dx, dy = 0, 1
        elif d == 2:
            dx, dy = -1, 0
        else:
            dx, dy = 0, -1
        xx = x + dx
        yy = y + dy
        if not(0 <= xx < H):
            continue
        if not(0 <= yy < W):
            continue
        if c[xx][yy] == "@":
            continue
        if (xx, yy) == (x2, y2):
            print(int(ceil(curr + 1 / K - EPS)))
            # print(*dist, sep="\n")
            return
        if dist[xx][yy] >= curr + 1 / K:
            dist[xx][yy] = curr + 1 / K
            heappush(stack, (int(ceil(curr + 1 / K - EPS)), xx, yy, (d - 1) % 4))
            heappush(stack, (int(ceil(curr + 1 / K - EPS)), xx, yy, (d + 1) % 4))
            heappush(stack, (curr + 1 / K, xx, yy, d))
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    seen = [[0 for c in input()] for i in range(H)]
    seen[x1][y1] = 1
    # table = [[-1] * H for _ in range(W)]
    # table[x1][y1] = 0
    # print(c)

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    while stack:
        curr, x, y, d = heappop(stack)
        # print(x, y, d, curr)
        if d == 0:
            flag = True
            for yy in range(y + 1, y + K + 1):
                if W <= yy:
                    flag = False
                    break
                # print(x, y, yy)
                if c[x][yy] == "@":
                    break
                if seen[x][yy] == 1:
                    continue
                if (x, yy) == (x2, y2):
                    print(curr + 1)
                    return
                # table[x][yy] = curr + 1
                heappush(stack, (curr + 1, x, yy, 2))
                heappush(stack, (curr + 1, x, yy, 3))
                seen[x][yy] = 1
            if flag:
                heappush(stack, (curr + 1, x, yy, 0))
        elif d == 1:
            flag = True
            for yy in range(y - 1, y - K - 1, -1):
                if 0 > yy:
                    flag = False
                    break
                if c[x][yy] == "@":
                    flag = False
                    break
                if seen[x][yy] == 1:
                    continue
                if (x, yy) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, x, yy, 2))
                heappush(stack, (curr + 1, x, yy, 3))
                seen[x][yy] = 1
            if flag:
                heappush(stack, (curr + 1, x, yy, 0))
        elif d == 2:
            flag = True
            for xx in range(x - 1, x - K - 1, -1):
                if 0 > xx:
                    flag = False
                    break
                if c[xx][y] == "@":
                    flag = False
                    break
                if seen[xx][y] == 1:
                    continue
                if (xx, y) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, xx, y, 0))
                heappush(stack, (curr + 1, xx, y, 1))
                seen[xx][y] = 1
            if flag:
                heappush(stack, (curr + 1, xx, y, 2))
        elif d == 3:
            flag = True
            for xx in range(x + 1, x + K + 1):
                if xx >= H:
                    flag = False
                    break
                if c[xx][y] == "@":
                    flag = False
                    break
                if seen[xx][y] == 1:
                    continue
                if (xx, y) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, xx, y, 0))
                heappush(stack, (curr + 1, xx, y, 1))
                seen[xx][y] = 1
            if flag:
                heappush(stack, (curr + 1, xx, y, 3))
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    W = W+2
    c = [["@"]*W]
    for i in range(H):
        c.append(["@"]+list(input())+["@"])
    c.append(["@"]*W)
    H = H+2

    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    # ヒープでなくて良い。
    # 高々1しか加わっていかないため、キューに加えられた順で十分昇順になる。
    Q = [(0, x1, y1, 0)]
    Q += [(0, x1, y1, 1)]
    Q += [(0, x1, y1, 2)]
    Q += [(0, x1, y1, 3)]
    i = 0
    while i < len(Q):
        curr, x, y, DXY = Q[i]
        c[x][y] = "@"
        dx, dy = DX[DXY], DY[DXY]
        for k in range(1, K+1):
            X, Y = x+k*dx, y+k*dy
            if c[X][Y] == "@":
                break
            if 0 < dist[X][Y] < curr+1:
                break
            # if dist[X][Y] == curr+1:
            #     continue
            dist[X][Y] = curr+1
            Q.append((curr+1, X, Y, (DXY+1) % 4))
            Q.append((curr+1, X, Y, (DXY-1) % 4))
        else:
            Q.append((curr+1, X, Y, DXY))
        if 0 < dist[x2][y2]:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    W = W+2
    c = [["@"]*W]
    for i in range(H):
        c.append(["@"]+list(input())+["@"])
    c.append(["@"]*W)
    H = H+2

    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    # ヒープでなくて良い。
    # 高々1しか加わっていかないため、キューに加えられた順で十分昇順になる。
    Q = [(0, x1, y1, 0)]
    Q += [(0, x1, y1, 1)]
    Q += [(0, x1, y1, 2)]
    Q += [(0, x1, y1, 3)]
    i = 0
    while i < len(Q):
        curr, x, y, DXY = Q[i]
        c[x][y] = "@"
        dx, dy = DX[DXY], DY[DXY]
        for k in range(1, K+1):
            X, Y = x+k*dx, y+k*dy
            if c[X][Y] == "@":
                break
            # if 0 < dist[X][Y] < curr+1:
            #     break
            # if dist[X][Y] == curr+1:
            #     continue
            dist[X][Y] = curr+1
            Q.append((curr+1, X, Y, (DXY+1) % 4))
            Q.append((curr+1, X, Y, (DXY-1) % 4))
        else:
            Q.append((curr+1, X, Y, DXY))
        if 0 < dist[x2][y2]:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1*M+y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, xy, DXY = Q[i]
        x, y = divmod(xy, M)
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if dist[X][Y] < curr+1:
                    break
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X*M+Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X*M+Y, flag))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            # print(*dist, sep="\n")
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    Q.append((0, (x1, y1), 0b1111))
    i = 0

    while i < len(Q):
        curr, (x, y), DXY = Q[i]
        # print([1 & (DXY >> l) for l in range(4)])
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if dist[X][Y] < curr+1:
                    break
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, (X, Y), flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, (X, Y), flag))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            # print(*dist, sep="\n")
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    Q.append((0, (x1, y1), (+1, 0)))
    Q.append((0, (x1, y1), (-1, 0)))
    Q.append((0, (x1, y1), (0, +1)))
    Q.append((0, (x1, y1), (0, -1)))
    i = 0
    while i < len(Q):
        curr, (x, y), (dx, dy) = Q[i]
        elseflag = False
        for k in range(1, K+1):
            X = x+k*dx
            Y = y+k*dy
            if not (0 <= X < H):
                break
            if not (0 <= Y < W):
                break
            if dist[X][Y] < curr+1:
                break
            if c[X][Y] == "@":
                break
            dist[X][Y] = curr+1
            Q.append((curr+1, (X, Y), (dy, dx)))
            Q.append((curr+1, (X, Y), (-dy, -dx)))
        else:
            # breakしなかったなら、同一方向をヒープへ追加
            Q.append((curr+1, (X, Y), (dx, dy)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import heapq
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []
    heapq.heappush(Q, (0, (x1, y1), (+1, 0)))
    heapq.heappush(Q, (0, (x1, y1), (-1, 0)))
    heapq.heappush(Q, (0, (x1, y1), (0, +1)))
    heapq.heappush(Q, (0, (x1, y1), (0, -1)))
    while Q:
        curr, (x, y), (dx, dy) = heapq.heappop(Q)
        elseflag = False
        for k in range(1, K+1):
            X = x+k*dx
            Y = y+k*dy
            if not (0 <= X < H):
                break
            if not (0 <= Y < W):
                break
            if dist[X][Y] < curr+1:
                break
            if c[X][Y] == "@":
                break
            dist[X][Y] = curr+1
            # 直交方向へ探索するようヒープに追加
            heapq.heappush(Q, (curr+1, (X, Y), (dy, dx)))
            heapq.heappush(Q, (curr+1, (X, Y), (-dy, -dx)))
        else:
            # breakしなかったなら、同一方向をヒープへ追加
            heapq.heappush(Q, (curr+1, (X, Y), (dx, dy)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            return
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import heapq
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []
    heapq.heappush(Q, (0, (x1, y1), (+1, 0)))
    heapq.heappush(Q, (0, (x1, y1), (-1, 0)))
    heapq.heappush(Q, (0, (x1, y1), (0, +1)))
    heapq.heappush(Q, (0, (x1, y1), (0, -1)))
    while Q:
        curr, (x, y), (dx, dy) = heapq.heappop(Q)
        elseflag = False
        for k in range(1, K+1):
            X = x+k*dx
            Y = y+k*dy
            if not (0 <= X < H):
                break
            if not (0 <= Y < W):
                break
            if dist[X][Y] < curr+1:
                break
            if c[X][Y] == "@":
                break
            dist[X][Y] = curr+1
            # 直交方向へ探索するようヒープに追加
            heapq.heappush(Q, (curr+1, (X, Y), (dy, dx)))
            heapq.heappush(Q, (curr+1, (X, Y), (-dy, -dx)))
        else:
            # breakしなかったなら、同一方向をヒープへ追加
            heapq.heappush(Q, (curr+1, (X, Y), (dx, dy)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            return
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import heapq
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = [(0, (x1, y1))]
    while Q:
        curr, (x, y) = heapq.heappop(Q)
        for dx, dy in zip(DX, DY):
            for k in range(1, K+1):
                # ヒープキューで管理していることから考えると
                # 値が存在する場所と比較しても更新できることはない。
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if dist[X][Y] < curr+1:
                    break
                if c[X][Y] == "@":
                    break
                # これ実質的に距離はcurrだけでよいのだけど
                dist[X][Y] = curr+1
                heapq.heappush(Q, (curr+1, (X, Y)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            # print(*dist, sep="\n")
            return
    print(-1)
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()