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):
import sys
from heapq import *
input = sys.stdin.readline


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    pond = [input().replace("\n", "") for _ in range(h)]
    
    dist_N = [[None]*w for _ in range(h)]
    dist_S = [[None]*w for _ in range(h)]
    dist_E = [[None]*w for _ in range(h)]
    dist_W = [[None]*w for _ in range(h)]
    
    already = [[[True]*4 for _ in range(w)] for _ in range(h)]
    
    not_yet = [(1, 0, sx-1, sy-1, "N"), (1, 0, sx-1, sy-1, "E"), (1, 0, sx-1, sy-1, "S"), (1, 0, sx-1, sy-1, "W")]
    heapify(not_yet)
    already[sx-1][sy-1][0] = False
    already[sx-1][sy-1][1] = False
    already[sx-1][sy-1][2] = False
    already[sx-1][sy-1][3] = False
    
    while not_yet:
        a, b, x, y, d = heappop(not_yet)
        if x != sx-1 or y != sy-1:
            if already[x][y][0]:
                already[x][y][0] = False
                not_yet.append((a, k-1, x, y, "N"))
            if already[x][y][1]:
                already[x][y][1] = False
                not_yet.append((a, k-1, x, y, "S"))
            if already[x][y][2]:
                already[x][y][2] = False
                not_yet.append((a, k-1, x, y, "W"))
            if already[x][y][3]:
                already[x][y][3] = False
                not_yet.append((a, k-1, x, y, "E"))
        if d == "N" and dist_N[x][y] == None:
            dist_N[x][y] = (a, b)
            if x > 0 and already[x-1][y][0] and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                already[x-1][y][0] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x-1, y, "N"))
                else:
                    not_yet.append((a, b+1, x-1, y, "N"))
        if d == "W" and dist_W[x][y] == None:
            dist_W[x][y] = (a, b)
            if y > 0 and already[x][y-1][2] and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                already[x][y-1][2] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x, y-1, "W"))
                else:
                    not_yet.append((a, b+1, x, y-1, "W"))
        if d == "S" and dist_S[x][y] == None:
            dist_S[x][y] = (a, b)
            if x < h-1 and already[x+1][y][1] and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                already[x+1][y][1] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x+1, y, "S"))
                else:
                    not_yet.append((a, b+1, x+1, y, "S"))
        if d == "E" and dist_E[x][y] == None:
            dist_E[x][y] = (a, b)
            if y < w-1 and already[x][y+1][3] and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                already[x][y+1][3] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x, y+1, "E"))
                else:
                    not_yet.append((a, b+1, x, y+1, "E"))
        
    gx -= 1
    gy -= 1
    ans = [10**7]
    
    for v in [dist_N[gx][gy], dist_S[gx][gy], dist_E[gx][gy], dist_W[gx][gy]]:
        if v != None:
            ans.append(v[0])
    
    answer = min(ans)
    print(-1 if answer == 10**7 else answer)
    
    print(dist_E)
        
        
    
    
    
    
if __name__ == "__main__":
    main()


import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()



Verdicts: Wrong Answer

Accepted