Problem p02644 (python)

Fixed submission:
from sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # surround the square with '@'
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))


    from random import randrange
    if randrange(0, 3) == 0:
        # BFS
        # 直線を進めるだけ進む
        from collections import deque
        seen = [[0] * (w+2) for _ in range(h+2)]
        seen[x1][y1] = 1
        todo = deque([(x1, y1)])
 
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
 
        while len(todo) > 0:
            ix, iy = todo.popleft()
            s = seen[ix][iy] + 1
 
            for j in range(4):
                jx, jy = ix, iy
                dxj, dyj = dx[j], dy[j]
 
                for _ in range(k):
                    jx, jy = jx + dxj, jy + dyj
 
                    if c[jx][jy] == '@':
                        break
 
                    if jx == x2 and jy == y2:
                        print(s - 1)
                        exit()
            
                    if seen[jx][jy] == 0:
                        seen[jx][jy] = s
                        todo.append((jx, jy))



    # Dijkstra
    seen = [[-1] * (w+2) for _ in range(h+2)]
    # todo[i] == (cost, x, y, direction)
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        # special case
        if seen[xi][yi] == cost:
            xj, yj = xi + dx[direction], yi + dy[direction]
            if c[xj][yj] == '.' and seen[xj][yj] == -1:
                heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue

        if seen[xi][yi] != -1:
            continue
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost-1)//k + 1)
            exit()
        
        # add
        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]

            if c[xj][yj] == '@':
                continue

            if seen[xj][yj] == -1:
                if j == direction:
                    heapq.heappush(todo, (cost+1, xj, yj, j))
                else:
                    heapq.heappush(todo, (((cost-1)//k + 1)*k + 1, xj, yj, j))

    print(-1)

main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # surround the square with '@'
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))

    # Dijkstra
    seen = [[0] * (w+2) for _ in range(h+2)]
    # todo.append((cost, x, y, direction))
    # direction:: None: -1, north: 0, east: 1, south: 2, west: 3
    todo = [(k, x1, y1, -1)]
    heapq.heapify(todo)

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        if seen[xi][yi] != 0:
            continue

        seen[xi][yi] = cost

        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]

            if c[xj][yj] == '@':
                continue

            if seen[xj][yj] == 0:
                if j == direction:
                    heapq.heappush(todo, (cost+1, xj, yj, j))
                else:
                    a, b = divmod(cost, k)
                    if b == 0:
                        heapq.heappush(todo, (cost+1, xj, yj, j))
                    else:
                        heapq.heappush(todo, (k*(a+1) + 1, xj, yj, j))
            
            if xj == x2 and yj == y2:
                if j == direction:
                    print(cost // k)
                else:
                    a, b = divmod(cost, k)
                    if b != 0:
                        ans = (a+1) * k
                    print(ans//k - 1)
                exit()

    print(-1)

main()