Problem:
 Score : 600 points    Problem Statement 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.      Constraints  1 \leq H,W,K \leq 10^6  H \times W \leq 10^6  1 \leq x_1,x_2 \leq H  1 \leq y_1,y_2 \leq W  x_1 \neq x_2 or y_1 \neq y_2 .  c_{i,j} is . or @ .  c_{x_1,y_1} =  .  c_{x_2,y_2} =  .  All numbers in input are integers.         Input Input is given from Standard Input in the following format:  H  W  K  x_1  y_1  x_2  y_2  c_{1,1}c_{1,2}  ..  c_{1,W}  c_{2,1}c_{2,2}  ..  c_{2,W}  :  c_{H,1}c_{H,2}  ..  c_{H,W}       Output Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2) , or print -1 if the travel is impossible.        Sample Input 1 3 5 2
3 2 3 4
.....
.@..@
..@..      Sample Output 1 5  Initially, Snuke is at the square (3,2) .
He can reach the square (3, 4) by making five strokes as follows:    From (3, 2) , go west one square to (3, 1) .    From (3, 1) , go north two squares to (1, 1) .    From (1, 1) , go east two squares to (1, 3) .    From (1, 3) , go east one square to (1, 4) .    From (1, 4) , go south two squares to (3, 4) .         Sample Input 2 1 6 4
1 1 1 6
......      Sample Output 2 2       Sample Input 3 3 3 1
2 1 2 3
.@.
.@.
.@.      Sample Output 3 -1

Solution (Python):

from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Solution (Python):

import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7

def array(*args, initial=0):
    pre = "[" * len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range(" + str(a) + ")]"
    S = pre + "{}".format(initial) + post
    return eval(S)


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = MAP()
    
    pond = array(H + 2, W + 2, 4, initial=-1)
    for h in range(1, H + 1):
        for w, c in enumerate(input(), start=1):
            if c == ".":
                for i in range(4):
                    pond[h][w][i] = INF
    
    q = deque()
    q.append(((0, 0), x1, y1, 0))
    q.append(((0, 0), x1, y1, 1))
    q.append(((0, 0), x1, y1, 2))
    q.append(((0, 0), x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while q:
        new_q = deque()
        while q:
            (a0, a1), x, y, d = q.popleft()
            
            nx = x + DX[d]
            ny = y + DY[d]
            
            if pond[nx][ny][0] == -1:     
                continue
            if pond[nx][ny][(d + 1) % 4] > a0 + 1:
                pond[nx][ny][(d + 1) % 4] = a0 + 1
                new_q.append(((a0 + 1, 0), nx, ny, (d + 1) % 4))
            if pond[nx][ny][(d - 1) % 4] > a0 + 1:
                pond[nx][ny][(d - 1) % 4] = a0 + 1
                new_q.append(((a0 + 1, 0), nx, ny, (d - 1) % 4))
            if pond[nx][ny][d] >= a0 + 1:
                pond[nx][ny][d] = a0 + 1
                if a1 + 1 < K:
                    q.append(((a0, a1 + 1), nx, ny, d))
                else:
                    new_q.append(((a0 + 1, 0), nx, ny, d))
            if (nx, ny) == (x2, y2):
                print(a0 + 1)
                return
        q = new_q
    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

def main():
    from heapq import heappush, heappop, heapify
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        new_stack = []
        while stack:
            curr, x, y, d = heappop(stack)
            dx, dy = DX[d], DY[d]
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * dx, y + k * dy
                if c[xx][yy] == 0:
                    b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d - 1) % 4))
                    b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d + 1) % 4))
                    c[xx][yy] = a
                elif c[xx][yy] != a:
                    flag = False
                    break
            if flag:
                heappush(new_stack, (a, xx, yy, d))
            if c[x2][y2] > 0:
                print(c[x2][y2], flush=True)
                exit(0)
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from heapq import heappush, heappop, heapify
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        new_stack = []
        while stack:
            curr, x, y, d = heappop(stack)
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if c[xx][yy] == 0:
                    b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d - 1) % 4))
                    b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d + 1) % 4))
                    c[xx][yy] = a
                elif c[xx][yy] != a:
                    flag = False
                    break
            if flag:
                heappush(new_stack, (a, xx, yy, d))
            if c[x2][y2] > 0:
                print(c[x2][y2])
                return
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    
    stack = deque([(x1, y1, 0), (x1, y1, 1),
                   (x1, y1, 2), (x1, y1, 3)])
    append, popleft = stack.append, stack.popleft
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        x, y, d = popleft()
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                if b == 0 or b == a + 1:
                    append((xx, yy, (d - 1) % 4))
                b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                if b == 0 or b == a + 1:
                    append((xx, yy, (d + 1) % 4))
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append((xx, yy, d))
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    
    stack = deque([((x1 * HH + y1) << 2) | 0, ((x1 * HH + y1) << 2) | 1,
                   ((x1 * HH + y1) << 2) | 2, ((x1 * HH + y1) << 2) | 3])
    append, popleft = stack.append, stack.popleft
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        b = popleft()
        d = b % 4
        x, y = divmod(b >> 2, HH)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                if b == 0 or b == a + 1:
                    append(((xx * HH + yy) << 2) + (d - 1) % 4)
                b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                if b == 0 or b == a + 1:
                    append(((xx * HH + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append(((xx * HH + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    
    stack = deque([((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
                   ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3])
    append, popleft = stack.append, stack.popleft
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        b = popleft()
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    
    stack = deque([((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
                   ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3])
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        b = stack.popleft()
        head += 1
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            stack.append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    
    stack = [((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
             ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while head < len(stack):
        b = stack[head]
        head += 1
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            stack.append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from heapq import heappush, heappop, heapify
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0

    
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    head = 0
    while head < len(stack):
        curr, x, y, d = stack[head]
        head += 1
        c[x][y] = "@"
        
        
        if d == 0:
            dx, dy = 1, 0
        elif d == 1:
            dx, dy = 0, 1
        elif d == 2:
            dx, dy = -1, 0
        else:
            dx, dy = 0, -1
        flag = True
        for i in range(1, K + 1):
            xx = x + i * dx
            yy = y + i * dy
            if not(0 <= xx < H) or not(0 <= yy < W) or c[xx][yy] == "@":
                flag = False
                break
            if (xx, yy) == (x2, y2):
                print(int(ceil(curr + 1 / K - EPS)))
                return
            if dist[xx][yy] > curr + 1:
                dist[xx][yy] = curr + 1
                stack.append((curr + 1, xx, yy, (d - 1) % 4))
                stack.append((curr + 1, xx, yy, (d + 1) % 4))
        if flag:
            if dist[xx][yy] >= curr + 1:
                stack.append((curr + 1, xx, yy, d))
    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):
INF=float('inf')
from collections import deque
def mbfs(G,sh,sw,H,W):
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0
    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            for k in range(1,K+1):
                nh=h+dx[dir]*k
                nw=w+dy[dir]*k
                if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    break
                if(G[nh][nw]=='@'):
                    break
                if(dist[nh][nw]<=dist[h][w]):
                    break
                if dist[nh][nw]==dist[h][w]+1:
                    continue
                else:
                    dist[nh][nw]=dist[h][w]+1
                    d.append([nh,nw])
    return dist
H,W,K=map(int,input().split())
sx,sy,gx,gy=map(lambda x:int(x)-1,input().split())
c=[list(input()) for i in range(H)]
dist=mbfs(c,sx,sy,H,W)
ans=dist[gx][gy]
print(ans if ans!=INF else -1)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
                    if ny == gy and nx == gx:
                        print(G[y][x] + 1)
                        return
    print(-1)
    return

solve()

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Solution (Python):
from queue import Queue


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(lambda z: int(z) - 1, input().split())
    c = [list(input().replace('\n', '')) for _ in range(h)]
    c[sx][sy] = 0
    q = Queue()
    q.put((sx, sy))
    while not q.empty():
        x, y = q.get()
        d = c[x][y]
        
        for i in range(1, k + 1):
            if x + i >= h:
                break
            if c[x + i][y] == '@':
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] < d + 1:
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] == d + 1:
                continue
            else:
                c[x + i][y] = d + 1
                q.put((x + i, y))
        
        for i in range(1, k + 1):
            if x - i < 0:
                break
            if c[x - i][y] == '@':
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] < d + 1:
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] == d + 1:
                continue
            else:
                c[x - i][y] = d + 1
                q.put((x - i, y))
        
        for i in range(1, k + 1):
            if y + i >= w:
                break
            if c[x][y + i] == '@':
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] < d + 1:
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] == d + 1:
                continue
            else:
                c[x][y + i] = d + 1
                q.put((x, y + i))
        
        for i in range(1, k + 1):
            if y - i < 0:
                break
            if c[x][y - i] == '@':
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] < d + 1:
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] == d + 1:
                continue
            else:
                c[x][y - i] = d + 1
                q.put((x, y - i))
    print(-1 if c[gx][gy] == '.' else c[gx][gy])


if __name__ == '__main__':
    main()

Solution (Python):
from queue import Queue


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(lambda z: int(z) - 1, input().split())
    c = [list(input().replace('\n', '')) for _ in range(h)]
    c[sx][sy] = 0
    q = Queue()
    q.put((sx, sy))
    while not q.empty():
        x, y = q.get()
        d = c[x][y]
        
        for i in range(1, k + 1):
            if x + i >= h:
                break
            if c[x + i][y] == '@':
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] < d + 1:
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] == d + 1:
                continue
            else:
                c[x + i][y] = d + 1
                q.put((x + i, y))
        
        for i in range(1, k + 1):
            if x - i < 0:
                break
            if c[x - i][y] == '@':
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] < d + 1:
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] == d + 1:
                continue
            else:
                c[x - i][y] = d + 1
                q.put((x - i, y))
        
        for i in range(1, k + 1):
            if y + i >= w:
                break
            if c[x][y + i] == '@':
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] < d + 1:
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] == d + 1:
                continue
            else:
                c[x][y + i] = d + 1
                q.put((x, y + i))
        
        for i in range(1, k + 1):
            if y - i < 0:
                break
            if c[x][y - i] == '@':
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] < d + 1:
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] < d + 1:
                continue
            else:
                c[x][y - i] = d + 1
                q.put((x, y - i))
    print(-1 if c[gx][gy] == '.' else c[gx][gy])


if __name__ == '__main__':
    main()

Solution (Python):

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True



dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d



dp = [MAX * (k + 1) + k] * (h * w * 4)


q = [((k + 1, convert(x1, y1, i))) for i in range(4)]

while q:
    c0, xyd = heappop(q)
    c1 = c0 // (k + 1)
    c2 = c0 % (k + 1)
    
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd] // (k + 1):
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > c1 * (k + 1) + c2 + 1:
                dp[nxyi] = c1 * (k + 1) + c2 + 1
                heappush(q, (dp[nxyi], nxyi))
        else:
            if dp[nxyi] > (c1 + 1) * (k + 1) + 1:
                dp[nxyi] = (c1 + 1) * (k + 1) + 1
                heappush(q, (dp[nxyi], nxyi))

ans = min(dp[convert(x2, y2, i)] // (k + 1) for i in range(4))
if ans == MAX:
    ans = -1
print(ans)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)