Problem p02644 (python)

Fixed submission:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**7]*w for _ in range(w)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or w <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

h, w, k = nm()
sy, sx, gy, gx = nm()
d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
sx -= 1; sy -= 1
gx -= 1; gy -= 1
C = [ns() for _ in range(w)]
G = [[10**10]*w for _ in range(h)]
G[sy][sx] = 0
q = deque([(sy, sx)])
while q:
    y, x = q.popleft()
    for i in range(4):
        dy, dx = d[i]
        ny, nx = y, x
        for _ in range(k):
            ny += dy; nx += dx
            if ny < 0 or h <= ny or nx < 0 or w <= nx:
                break
            if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                break
            if G[ny][nx] > G[y][x] + 1:
                G[ny][nx] = G[y][x] + 1
                q.append((ny, nx))
ans = G[gy][gx]
print(ans if ans < 10**10 else -1)

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**10]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**10 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    geta = 20
    mask = (1 << geta) - 1
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**10]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy<<geta) + sx])
    while q:
        v = q.popleft()
        y = v >> geta; x = v & mask
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx or C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny<<geta) + nx)
    ans = G[gy][gx]
    print(ans if ans < 10**10 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**10]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx or C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**10 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[[10**10]*w for _ in range(h)] for i in range(4)]
    for i in range(4):
        G[i][sy][sx] = 0
    q = deque([(sy, sx, i, 0) for i in range(4)])
    while q:
        y, x, t, c = q.popleft()
        if c:
            dy, dx = d[t]
            ny = y + dy; nx = x + dx
            if 0 <= ny < h and 0 <= nx < w and C[ny][nx] != '@' and G[t][ny][nx] > G[t][y][x]:
                G[t][ny][nx] = G[t][y][x]
                q.appendleft((ny, nx, t, c-1))
        for i in range(4):
            dy, dx = d[i]
            ny = y + dy; nx = x + dx
            if 0 <= ny < h and 0 <= nx < w and C[ny][nx] != '@' and G[i][ny][nx] > G[t][y][x] + 1:
                G[i][ny][nx] = G[t][y][x] + 1
                q.append((ny, nx, i, k-1))
    ans = min(G[i][gy][gx] for i in range(4))
    print(ans if ans < 10**10 else -1)
    return

solve()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[[10**10]*w for _ in range(h)] for i in range(4)]
    for i in range(4):
        G[i][sy][sx] = 0
    q = deque([(sy, sx, i, 0) for i in range(4)])
    while q:
        y, x, t, c = q.popleft()
        dy, dx = d[t]
        ny = y + dy; nx = x + dx
        if 0 <= ny < h and 0 <= nx < w and C[ny][nx] != '@' and G[t][ny][nx] > G[t][y][x] + (c == 0):
            G[t][ny][nx] = G[t][y][x] + (c == 0)
            if c:
                q.appendleft((ny, nx, t, c-1))
            else:
                q.append((ny, nx, t, k-1))
        for i in range(4):
            if i == t:
                continue
            dy, dx = d[i]
            ny = y + dy; nx = x + dx
            if 0 <= ny < h and 0 <= nx < w and C[ny][nx] != '@' and G[i][ny][nx] > G[t][y][x] + 1:
                G[i][ny][nx] = G[t][y][x] + 1
                q.append((ny, nx, i, k-1))
    ans = min(G[i][gy][gx] for i in range(4))
    print(ans if ans < 10**10 else -1)
    return

solve()