Problem p02644 (python)

Fixed submission:
Dy = [0,1,0,-1]
Dx = [1,0,-1,0]
H, W, K = map(int, input().split())
y1,x1,y2,x2 = map(int, input().split())
C = ["@" + input() + "@" for _ in range(H)]
C = ["@"*(W+2)] + C + ["@"*(W+2)]
L = [[1]*(W+2) for _ in range(H+2)]
R = [[1]*(W+2) for _ in range(H+2)]
U = [[1]*(W+2) for _ in range(H+2)]
D = [[1]*(W+2) for _ in range(H+2)]
q = [(y1, x1)]
ans = 0
while q:
    q_new = []
    for y0, x0 in q:
        if (y0, x0) == (y2, x2):
            print(ans)
            exit()
        for dy, dx, Next in zip(Dy, Dx, [L, R, U, D]):
            y, x = y0, x0
            sum_next = 0
            Path = [(y, x)]
            while True:
                sum_next += Next[y][x]
                y = y0 + dy * sum_next
                x = x0 + dx * sum_next
                if sum_next > K:
                    break
                if C[y][x] == "@":
                    break
                Path.append((y, x))
                q_new.append((y, x))
            for path_y, path_x in Path:
                Next[path_y][path_x] = abs(path_y-y) + abs(path_x-x)
    q = q_new
    ans += 1

print(-1)

Buggy submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Closed = [[False]*(W+2) for _ in range(H+2)]
    Nexts = [[[(y+dy, x+dx) for x in range(W+2)] for y in range(H+2)] for dy, dx in zip(Dy, Dx)]
    def root(y, x, Next):
        yp, xp = Next[y][x]
        if not Closed[yp][xp]:
            return yp, xp
        else:
            yp, xp = root(yp, xp, Next)
            Next[y][x] = (yp, xp)
            return yp, xp
    def remove(y, x):
        for i in range(2):
            y1, x1 = Nexts[i][y][x]
            y2, x2 = Nexts[i+2][y][x]
            Nexts[i+2][y1][x1] = (y2, x2)
            Nexts[i][y2][x2] = (y1, x1)
        Closed[y][x] = True
    q = [(y1, x1)]
    remove(y1, x1)
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for Next in Nexts:
                while True:
                    y, x = root(y0, x0, Next)
                    if abs(y-y0)+abs(x-x0) > K or C[y][x] != ".":
                        break
                    remove(y, x)
                    q_new.append((y, x))
        q = q_new
        ans += 1
    print(-1)

main()

Buggy submission (verdict: Runtime Error):
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Closed = [[False]*(W+2) for _ in range(H+2)]
    Nexts = [[[(y+dy, x+dx) for x in range(W+2)] for y in range(H+2)] for dy, dx in zip(Dy, Dx)]
    def root(y, x, Next):
        yp, xp = Next[y][x]
        if not Closed[yp][xp]:
            return yp, xp
        else:
            yp, xp = root(yp, xp, Next)
            Next[y][x] = (yp, xp)
            return yp, xp
    def remove(y, x):
        for i in range(2):
            y1, x1 = Nexts[i][y][x]
            y2, x2 = Nexts[i+2][y][x]
            Nexts[i+2][y1][x1] = (y2, x2)
            Nexts[i][y2][x2] = (y1, x1)
        Closed[y][x] = True
    q = [(y1, x1)]
    remove(y1, x1)
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for Next in Nexts:
                while True:
                    y, x = root(y0, x0, Next)
                    if abs(y-y0)+abs(x-x0) > K or C[y][x] != ".":
                        break
                    remove(y, x)
                    q_new.append((y, x))
        q = q_new
        ans += 1
    print(-1)

main()

Buggy submission (verdict: Runtime Error):
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Nexts = [[[1]*(W+2) for _ in range(H+2)] for _ in range(4)]
    q = [(y1, x1)]
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for dy, dx, Next in zip(Dy, Dx, Nexts):
                y, x = y0, x0
                sum_next = 0
                Path = [(y, x)]
                while True:
                    sum_next += Next[y][x]
                    y = y0 + dy * sum_next
                    x = x0 + dx * sum_next
                    if sum_next > K or C[y][x] != ".":
                        break
                    Path.append((y, x))
                    q_new.append((y, x))
                for path_y, path_x in Path:
                    Next[path_y][path_x] = abs(path_y-y) + abs(path_x-x)
        q = q_new
        ans += 1
    print(-1)

main()