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):
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))

    
    # 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)

        
        if seen[xi][yi] != -1:
            if seen[xi][yi] == cost:
                xj, yj = xi + dx[direction], yi + dy[direction]
                if c[xj][yj] == '.' and (seen[xj][yj] == -1 or (seen[xj][yj]+k-1)//k * k > cost):
                    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 - 1)
            exit()
        
        # add
        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()

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))

    
    # 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)

        
        if seen[xi][yi] != -1:
            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
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost+k-1)//k)
            for i in seen:
                print(i)
            exit()
        
        # add
        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.' and seen[xj][yj] == -1:
                if j == direction:
                    heapq.heappush(todo, (cost+1, xj, yj, j))
                else:
                    heapq.heappush(todo, ((cost+k-1)//k * k + 1, xj, yj, j))

    print(-1)

main()

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))

    
    # 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)

        
        if seen[xi][yi] != -1:
            if seen[xi][yi] == cost:
                xj, yj = xi + dx[direction], yi + dy[direction]
                if c[xj][yj] == '.' and (seen[xj][yj] == -1 or (seen[xj][yj]+k-1)//k * k > cost):
                    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 + 1)
            exit()
        
        # add
        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()

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))

    
    # 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)

        
        if seen[xi][yi] != -1:
            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
        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] == '.' and 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()

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))

    
    # 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)

        
        if seen[xi][yi] != -1:
            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
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost-1)//k)
            exit()
        
        # add
        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.' and 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()

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))

    
    # 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)

        
        if seen[xi][yi] != -1:
            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
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost)//k + 1)
            exit()
        
        # add
        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.' and 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()

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 = 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()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted