Problem p02644 (python)

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 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()

Buggy 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()

Buggy 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()