Problem p02644 (python)

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        #if dist[i][j] < d:
        #    continue
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 > dist[nxt_i][nxt_j]:
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[[INF] * w for _ in range(h)] for _ in range(4)]
    dist[U][i1][j1] = 0
    q = deque([(0, U, i1, j1)])
    while q:
        d, dire, i, j = q.popleft()

        for cnt in range(1, 4):
            if d < dist[(dire + cnt) % 4][i][j]:
                dist[(dire + cnt) % 4][i][j] = d
                q.appendleft((d, (dire + cnt) % 4, i, j))

        if dire == U:
            for length in range(1, k + 1):
                nxt_i = i - length
                if 0 <= nxt_i and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == D:
            for length in range(1, k + 1):
                nxt_i = i + length
                if nxt_i < h and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == L:
            for length in range(1, k + 1):
                nxt_j = j - length
                if 0 <= nxt_j and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break
        if dire == R:
            for length in range(1, k + 1):
                nxt_j = j + length
                if nxt_j < w and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break

    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = min([dist[i][x2][y2] for i in range(4)])

if ans == 10 ** 18:
    print(re)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[[INF] * w for _ in range(h)] for _ in range(4)]
    dist[U][i1][j1] = 0
    q = deque([(0, U, i1, j1)])
    while q:
        d, dire, i, j = q.popleft()
        if dist[dire][i][j] < d:
            continue
        for cnt in range(1, 4):
            if d < dist[(dire + cnt) % 4][i][j]:
                dist[(dire + cnt) % 4][i][j] = d
                q.appendleft((d, (dire + cnt) % 4, i, j))

        if dire == U:
            for length in range(1, k + 1):
                nxt_i = i - length
                if 0 <= nxt_i and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == D:
            for length in range(1, k + 1):
                nxt_i = i + length
                if nxt_i < h and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == L:
            for length in range(1, k + 1):
                nxt_j = j - length
                if 0 <= nxt_j and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break
        if dire == R:
            for length in range(1, k + 1):
                nxt_j = j + length
                if nxt_j < w and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break

    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = min([dist[i][x2][y2] for i in range(4)])

if ans == 10 ** 18:
    print(re)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline


def dijkstra(i1, j1) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 9
    dist = [[[INF] * w for _ in range(h)] for _ in range(4)]
    dist[U][i1][j1] = 0
    q = deque([(0, U, i1, j1)])   # q = [(startからの距離, 現在地)]
    while q:
        d, dire, i, j = q.popleft()
        if dist[dire][i][j] < d:
            continue
        for cnt in range(1, 4):
            if dist[dire][i][j] < dist[(dire + cnt) % 4][i][j]:
                dist[(dire + cnt) % 4][i][j] = dist[dire][i][j]
                q.appendleft((dist[dire][i][j], (dire + cnt) % 4, i, j))
        if dire == U:
            for length in range(1, k + 1):
                nxt_i = i - length
                if 0 <= nxt_i and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == D:
            for length in range(1, k + 1):
                nxt_i = i + length
                if nxt_i < h and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == L:
            for length in range(1, k + 1):
                nxt_j = j - length
                if 0 <= nxt_j and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, i, nxt_j))
                else:
                    break
        if dire == R:
            for length in range(1, k + 1):
                nxt_j = j + length
                if nxt_j < w and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, i, nxt_j))
                else:
                    break

    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = dijkstra(x1, y1)
ans = min([dist[i][x2][y2] for i in range(4)])

if ans == 10 ** 9:
    print(-1)
else:
    print(ans)