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):
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  
                    break
                if y2 < 0 or y2 >= W:  
                    break
                if m[x2][y2] == '@':  
                    break
                if M[x2][y2] < d + 1:  
                    break
                if M[x2][y2] == d + 1:  
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Solution (Python):
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

                
                
                
                
                
                
                
                
                
                
                
                
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Solution (Python):
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                
                
                
                
                
                
                
                
                
                

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)

Solution (Python):
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Solution (Python):
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Solution (Python):
from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))  
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])

Solution (Python):
from collections import deque
import sys


def bfs(xs, ys, d):
    queue = deque()
    queue.append((xs, ys, d))
    M[xs][ys] = d
    while queue:
        
        x1, y1, d = queue.popleft()  
        if [x1, y1] == [xg, yg]:  
            return

        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:  
                        M[x2][y2] = d + 1
                        queue.append((x2, y2, d + 1))  
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])

Solution (Python):
from collections import deque
import sys


def bfs(xs, ys):
    queue = deque([[xs, ys]])
    M[xs][ys] = 0
    while queue:
        
        x1, y1 = queue.popleft()  
        if [x1, y1] == [xg, yg]:  
            return M[x1][y1]

        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys)

print(M[xg][yg])

Solution (Python):
from collections import deque
import sys


def bfs(M, sy, sx):
    queue = deque([[xs, ys]])
    M[sy][sx] = 0
    while queue:
        
        x1, y1 = queue.popleft()  
        if [x1, y1] == [xg, yg]:  
            return M[x1][y1]
        
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(M, xs, ys)

print(M[xg][yg])

Solution (Python):
from collections import deque
import sys

def bfs(M, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    M[sy][sx] = 0
    while queue:
        
        y, x = queue.popleft()  
        if [y, x] == [gy, gx]:  
            return M[y][x]
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k

                if (0 <= new_y < H) and (0 <= new_x < W):
                    if m[new_y][new_x] == "@":
                        break
                    elif M[new_y][new_x] == -1:  
                        M[new_y][new_x] = M[y][x] + 1
                        queue.append([new_y, new_x])  
                    elif M[new_y][new_x] < M[y][x] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))
    
M = [[-1] * W for i in range(H)]

bfs(M, x1, y1, x2, y2)

print(M[x2][y2])

Solution (Python):
from collections import deque


def bfs(visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        
        y, x = queue.popleft()  
        if [y, x] == [gy, gx]:  
            return visited[y][x]
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k

                if (0 <= new_y < H) and (0 <= new_x < W):
                    if m[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
m = []
for i in range(H):
    m.append(str(input()))
visited = [[-1] * W for i in range(H)]
bfs(visited, x1, y1, x2, y2)
print(visited[x2][y2])

Solution (Python):
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        
        y, x = queue.popleft()  
        if [y, x] == [gy, gx]:  
            return visited[y][x]
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x + dx * k
                new_y = y + dy * k
                
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)

print(visited[x2][y2])

Solution (Python):
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        
        y, x = queue.popleft()  
        if [y, x] == [gy, gx]:  
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)

print(visited[x2][y2])

Solution (Python):
import collections
H,W,K = map(int,input().split())
s1,e1,s2,e2 = map(int,input().split())
s1-=1
e1-=1
s2-=1
e2-=1
L = []
board = []
for _ in range(H):
    a = input()
    L.append(a)
for i in range(H):
    l = L[i]
    tmp = []
    for j in range(len(l)):
        tmp.append(l[j])
    board.append(tmp)

queue = collections.deque()
queue.append([0,s1,e1])
seen = [[float('inf')]*(W) for _ in range(H)]
destination = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
    cost,x,y = queue.popleft()
    seen[x][y] = cost
    if x==s2 and y ==e2:
        print(cost);exit()
        break
    for dx,dy in destination:
        X,Y = x,y
        for i in range(1,K+1):
            NX = X +i*dx
            NY = Y + i*dy
            if 0>NX or NX>=H or 0>NY or NY>=W or seen[NX][NY] < seen[X][Y]+1: break
            else:
                if board[NX][NY]=='@':
                    break
                elif seen[NX][NY] ==float('inf'):
                    queue.append([cost+1,NX,NY])
                    seen[NX][NY] = cost+1

print(-1)

Solution (Python):
from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [input() for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                ny, nx = y+dy*j, x+dx*j
                if (not (0<=ny<H and 0<=nx<W)) or l[ny][nx]=="@" or dist[(ny, nx)] < dist[(y, x)] + 1:
                    break
                if dist[(ny, nx)] > dist[(y, x)] + 1:
                    dist[(ny, nx)] = dist[(y, x)] + 1
                    q.append((ny, nx))
                else:
                    continue

    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                ny, nx = y+dy*j, x+dx*j
                if (not (0<=ny<H and 0<=nx<W)) or l[ny][nx] or dist[(ny, nx)] < dist[(y, x)] + 1:
                    break
                if dist[(ny, nx)] > dist[(y, x)] + 1:
                    dist[(ny, nx)] = dist[(y, x)] + 1
                    q.append((ny, nx))
                else:
                    continue

    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if (not (0<=y+dy*j<H and 0<=x+dx*j<W)) or l[y+dy*j][x+dx*j] or dist[(y+dy*j, x+dx*j)] < dist[(y, x)] + 1:
                    break
                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                else:
                    continue

    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

c = [input().rstrip() for _ in range(H)]

d = deque([(x1-1, y1-1)])

dp = [[-1] * W for _ in range(H)]
dp[x1-1][y1-1] = 0

while d:
    x, y = d.popleft()
    if x == x2-1 and y == y2-1:
        print(dp[x][y])
        break

    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        for i in range(1, K+1):
            nx = x + dx * i
            ny = y + dy * i

            if 0 > nx or nx >= H or 0 > ny or ny >= W or c[nx][ny] == '@':
                break

            if dp[nx][ny] == -1:
                dp[nx][ny] = dp[x][y] + 1
                d.append((nx, ny))
            elif dp[nx][ny] <= dp[x][y]:
                break
else:
    print(-1)

Solution (Python):
from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                elif dist[(y+dy*j, x+dx*j)] == dist[(y, x)] + 1:
                    continue
                else:
                    break


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

from collections import deque
INF = float('inf')
def resolve():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(lambda x:int(x)-1, input().split())
    G = [list(input()) for _ in range(H)]

    dist = [[INF] * W for i in range(H)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])

    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy):
            print(dist[x][y])
            return
        for dx, dy in drc:
            nx = x
            ny = y
            for k in range(K):
                nx += dx
                ny += dy
                if 0 <= nx < H and 0 <= ny < W and G[nx][ny] != '@':
                    if dist[nx][ny] <= dist[x][y]:
                        break
                    if dist[nx][ny] == INF:
                        q.append((nx, ny))
                    dist[nx][ny] = dist[x][y] + 1
                else:
                    break
    print(-1)

if __name__ == "__main__":
    resolve()

Solution (Python):
def main():
  h,w,k=map(int,input().split())
  si,sj,ti,tj=map(int,input().split())
  si-=1
  sj-=1
  ti-=1
  tj-=1
  b=[input()for _ in range(h)]
  ans=[[-1]*w for _ in range(h)]
  ans[si][sj]=0
  from collections import deque
  d=deque()
  d.append((si,sj))
  while d:
    x,y=d.popleft()
    if x==ti and y==tj:
      exit(print(ans[x][y]))
    for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
      for i in range(1,k+1):
        xx=x+dx*i
        yy=y+dy*i
        if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
        if 0<=ans[xx][yy]<=ans[x][y]:break
        if ans[xx][yy]==-1:d.append((xx,yy))
        ans[xx][yy]=ans[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    h,w,k=MI()
    x1,y1,x2,y2=MI1()
    aa=[[0 if c=="@" else inf for c in SI()] for _ in range(h)]
    

    aa[x1][y1]=0
    q=deque()
    q.append((x1,y1,0))
    while q:
        x,y,d=q.popleft()
        for nx in range(x+1,min(x+k+1,h)):
            if aa[nx][y] == d + 1:continue
            if aa[nx][y]<d+1:break
            aa[nx][y]=d+1
            q.append((nx,y,d+1))
        for nx in range(x-1,max(x-k-1,-1),-1):
            if aa[nx][y] == d + 1:continue
            if aa[nx][y]<d+1:break
            aa[nx][y]=d+1
            q.append((nx,y,d+1))
        for ny in range(y+1,min(y+k+1,w)):
            if aa[x][ny] == d + 1:continue
            if aa[x][ny]<d+1:break
            aa[x][ny]=d+1
            q.append((x,ny,d+1))
        for ny in range(y-1,max(y-k-1,-1),-1):
            if aa[x][ny] == d + 1:continue
            if aa[x][ny]<d+1:break
            aa[x][ny]=d+1
            q.append((x,ny,d+1))
        
        

    ans=aa[x2][y2]
    if ans==inf:print(-1)
    else:print(ans)

main()

Solution (Python):
from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(4):
        for j in range(1,k+1):
            nx = bx+dx[i]*j
            ny = by+dy[i]*j
            if 0 > nx or 0 > ny or nx >= he  or ny >= w:
                break
            if l[nx][ny] == "@":
                break
            if d[nx][ny] <= dis:
                break
            if d[nx][ny] > dis+1:
                d[nx][ny] = dis+1
                q.append((dis+1,nx,ny))

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])

Solution (Python):

from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return map(int, input().split())
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    h, w, K = LI()
    y1, x1, y2, x2 = LI()
    q = deque()
    field = [[False] * (w + 2)] + [None] * h + [[False] * (w + 2)]
    for i in range(1, h + 1):
        field[i] = [False] + [True] * w + [False]
    for i in range(1, h + 1):
        s = input().rstrip()
        for j in range(1, w + 1):
            if s[j-1] == "@":
                field[i][j] = False
    q.append((x1, y1))
    ans = 0
    c = [[0] * (w + 2) for i in range(h + 2)]
    while q:
        next_q = deque()
        while q:
            x, y = q.pop()
            if (x, y) == (x2, y2):
                print(ans)
                return
            for i in range(1, K + 1):
                if field[y + i][x]:
                    if not c[y + i][x]:
                        next_q.append((x, y + i))
                        c[y + i][x] = 1
                else:
                    break
            for i in range(1, K + 1):
                if field[y][x + i]:
                    if not c[y][x + i]:
                        next_q.append((x + i, y))
                        c[y][x + i] = 1
                else:
                    break
            for i in range(1, K + 1):
                if field[y - i][x]:
                    if not c[y - i][x]:
                        next_q.append((x, y - i))
                        c[y - i][x] = 1
                else:
                    break
            for i in range(1, K + 1):
                if field[y][x - i]:
                    if not c[y][x - i]:
                        next_q.append((x - i, y))
                        c[y][x - i] = 1
                else:
                    break
            field[y][x] = False
        ans += 1
        q = next_q
    print(-1)
    return



if __name__ == '__main__':
    solve()