Problem: Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.  Some of the squares have a lotus leaf on it and cannot be entered. The square (i,j) has a lotus leaf on it if c_{ij} is `@`, and it does not if c_{ij} is `.`.  In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.  Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Submission attempts (in order):

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 = input()
        l = ['@']
        for j in i:
            l.append(j)
        l.append('@')
        c.append(l)
    c.append(['@'] * (w+2))
 
    
    # seen[x][y] = the minimum cost of (x, y)
    # if seen[x][y] == -1, (x, y) is unresearched
    seen = [[-1] * (w+2) for _ in range(h+2)]
 
    
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)
 
    # direction
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)
 
        # only straight
        if seen[xi][yi] != -1:
            if (seen[xi][yi]+k-1)//k * k > cost:
                xj, yj = xi + dx[direction], yi + dy[direction]
                if c[xj][yj] == '.':
                    heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue
        seen[xi][yi] = cost
 
        # goal
        if xi == x2 and yi == y2:
            print((cost+k-1)//k)
            exit()
        
        # 4 directions
        for j in range(4):
            xj, yj = xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.':
                if j == direction:
                    if seen[xj][yj] == -1 or (seen[xj][yj]+k-1)//k * k > cost:
                        heapq.heappush(todo, (cost+1, xj, yj, j))
                elif seen[xj][yj] == -1:
                    heapq.heappush(todo, ((cost+k-1)//k * k + 1, xj, yj, j))
 
    print(-1)
 
main()

import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')
 
 
def main():
    H, W, K = map(int, readline().split())
    x1, y1, x2, y2 = map(int, readline().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    C = read().split()
 
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0
    d = deque([[x1, y1]])
    dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while d:
        x, y = d.popleft()
        if (x, y) == (x2, y2):
            print(dist[x][y])
            quit()
        for dx, dy in dxy:
            xx = x
            yy = y
            for i in range(K):
                xx += dx;
                yy += dy
                if 0 <= xx < H and 0 <= yy < W and C[xx][yy] != '@':
                    if dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == INF:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break
 
    print(-1)
 
 
if __name__ == '__main__':
    main()

Verdicts: Runtime Error

Accepted