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 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():
    mxy = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    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
            if field[y][x]:
                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()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
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():
    mxy = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    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
            if field[y][x]:
                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()

Solution (Python):
def f_pond_skater():
    from heapq import heappush, heappop
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    heap = []
    dist = [[float('inf')] * W for _ in range(H)]
    dist[start_row][start_col] = 0

    diff = ((0, 1), (1, 0), (0, -1), (-1, 0))
    heappush(heap, (0, start_row, start_col))
    while heap:
        cost, row, col = heappop(heap)
        cost_next = cost + 1

        if row == target_row and col == target_col:
            return cost

        for dr, dc in diff:
            nr, nc = row, col
            for _ in range(K):
                nr += dr
                nc += dc
                if not (0 <= nr < H and 0 <= nc < W) or Grid[nr][nc] == '@':
                    break
                if dist[nr][nc] > cost_next:
                    dist[nr][nc] = cost_next
                    heappush(heap, (cost_next, nr, nc))
                elif dist[nr][nc] == cost_next:
                    continue
                else:
                    break
    return -1

print(f_pond_skater())

Solution (Python):
from collections import deque
h,w,k = map(int,input().split())
y1,x1,gy,gx = map(int,input().split())
m = ["@"*(w+2)]+["@"+input()+"@" for i in range(h)]+["@"*(w+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq=deque([(y1,x1)])
ans = 0
temp = [[-1]*(w+2) for i in range(h+2)]
temp[y1][x1] = 0
cnt = 0
while dq:
    
    
    y,x = dq.popleft()
    
    for j in opt:
        y1 = y+j[0]
        x1 = x+j[1]
        if m[y1][x1] == "@":
            
            continue
        if temp[y1][x1] == -1 or temp[y1][x1]-temp[y][x]>0:
            for i in range(k):
                if (temp[y1+i*j[0]][x1+i*j[1]] == -1 or temp[y1+i*j[0]][x1+i*j[1]]-temp[y][x]>0) and m[y1+i*j[0]][x1+i*j[1]] == ".":
                    if temp[y1+i*j[0]][x1+i*j[1]]-temp[y][x]==1:
                        continue
                    temp[y1+i*j[0]][x1+i*j[1]] = temp[y][x]+1
                    dq.append((y1+i*j[0],x1+i*j[1]))
                    
                else:
                    
                    break
    
    

print(temp[gy][gx])

Solution (Python):
from collections import deque
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

maze = []
maze.append(["@"]*(W+2))
for _ in range(H):
  row = list(input())
  maze.append(["@"]+row+["@"])
maze.append(["@"]*(W+2))

q = deque([(x1,y1)])
depth = 0
while q:
  for i,j in q:
    maze[i][j] = "@"

  new_q = set()
  l = len(q)
  for _ in range(l):
    x,y = q.pop()
    if (x,y) == (x2,y2):
      print(depth)
      exit()

    
    for i in range(1, K+1):
      if maze[x-i][y] == "@": break
      new_q.add((x-i, y))

    
    for i in range(1, K+1):
      if maze[x+i][y] == "@": break
      new_q.add((x+i, y))

    
    for i in range(1, K+1):
      if maze[x][y-i] == "@": break
      new_q.add((x, y-i))

    
    for i in range(1, K+1):
      if maze[x][y+i] == "@": break
      new_q.add((x, y+i))

  q = deque(list(new_q))
  depth += 1

print(-1)

Solution (Python):
from collections import deque
h,w,k = map(int,input().split())
y1,x1,gy,gx = map(int,input().split())
m = ["@"*(w+2)]+["@"+input()+"@" for i in range(h)]+["@"*(w+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq=deque([(y1,x1)])
ans = 0
temp = [[-1]*(w+2) for i in range(h+2)]
temp[y1][x1] = 0
cnt = 0
while dq:
    
    
    y,x = dq.popleft()
    
    for j in opt:
        y1 = y+j[0]
        x1 = x+j[1]
        if m[y1][x1] == "@":
            
            continue
        if temp[y1][x1] == -1 or temp[y1][x1]-temp[y][x]>0:
            for i in range(k):
                if (temp[y1+i*j[0]][x1+i*j[1]] == -1 or temp[y1+i*j[0]][x1+i*j[1]]-temp[y][x]>0) and m[y1+i*j[0]][x1+i*j[1]] == ".":
                    if temp[y1+i*j[0]][x1+i*j[1]]-temp[y][x]==1:
                        continue
                    temp[y1+i*j[0]][x1+i*j[1]] = temp[y][x]+1
                    dq.append((y1+i*j[0],x1+i*j[1]))
                    
                else:
                    
                    break
    
    

print(temp[gy][gx])

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            for k in range(1, K+1):
                h2 = h + dh*k
                w2 = w + dw*k
                if grid[h2][w2] == '@':
                    break
                
                if dist[h2][w2] < dist[h][w] + 1:
                    break
                elif dist[h2][w2] == dist[h][w] + 1:
                    continue
                else:
                    dist[h2][w2] = dist[h][w] + 1
                    que.append((h2, w2))
    return dist

H, W, K = MAP()
x1, y1, x2, y2 = MAP()
grid = build_grid(H, W, '@', str, space=0, padding=1)

res = bfs(grid, [(x1, y1)])
ans = res[x2][y2]
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split());b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0;d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=j:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Solution (Python):
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=j:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Solution (Python):
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=j:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    x1,y1,x2,y2 = map(int,ipt().split())
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    ms = [input()+"@" for _ in range(h)]
    ms.append("@"*(w+1))
    hq = []
    al = [[10**18]*w for _ in range(h)]
    al[x1][y1] = 0
    dr = [(0,1),(1,0),(0,-1),(-1,0)]
    hpq.heappush(hq,(0,x1,y1))
    while hq:
        c,x,y = hpq.heappop(hq)
        cn = c+1
        if x == x2 and y == y2:
            print(c)
            exit()
        for dx,dy in dr:
            xx = x
            yy = y
            for i in range(k):
                xx += dx
                yy += dy
                if ms[xx][yy] == ".":
                    if al[xx][yy] > cn:
                        al[xx][yy] = cn
                        hpq.heappush(hq,(cn,xx,yy))
                    elif al[xx][yy] == cn:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)

    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
sx, sy, tx, ty = map(lambda a: int(a) - 1, input().split())
INF = 10**18

A = [input() for _ in range(H)]

minDist = [[INF] * W for _ in range(H)]
minDist[sx][sy] = 0
que = deque([(0, sx, sy)])

while que:
    dist, nx, ny = que.popleft()
    if nx == tx and ny == ty:
        break

    for i in range(1, K + 1):
        if nx + i >= H:
            break
        if minDist[nx + i][ny] <= dist or A[nx + i][ny] == '@':
            break
        if minDist[nx + i][ny] > dist + 1:
            minDist[nx + i][ny] = dist + 1
            que.append((dist + 1, nx + i, ny))
    for i in range(1, K + 1):
        if nx - i < 0:
            break
        if minDist[nx - i][ny] <= dist or A[nx - i][ny] == '@':
            break
        if minDist[nx - i][ny] > dist + 1:
            minDist[nx - i][ny] = dist + 1
            que.append((dist + 1, nx - i, ny))
    for i in range(1, K + 1):
        if ny + i >= W:
            break
        if minDist[nx][ny + i] <= dist or A[nx][ny + i] == '@':
            break
        if minDist[nx][ny + i] > dist + 1:
            minDist[nx][ny + i] = dist + 1
            que.append((dist + 1, nx, ny + i))
    for i in range(1, K + 1):
        if ny - i < 0:
            break
        if minDist[nx][ny - i] <= dist or A[nx][ny - i] == '@':
            break
        if minDist[nx][ny - i] > dist + 1:
            minDist[nx][ny - i] = dist + 1
            que.append((dist + 1, nx, ny - i))

ans = minDist[tx][ty]
print(ans if ans < INF else -1)

Solution (Python):
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

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

H, W, K = map(int, input().split())
sx, sy, tx, ty = map(lambda a: int(a) - 1, input().split())
INF = 10**18

A = [input().decode() for _ in range(H)]

minDist = [[INF] * W for _ in range(H)]
minDist[sx][sy] = 0
que = deque([(0, sx, sy)])

while que:
    dist, nx, ny = que.popleft()

    for i in range(1, K + 1):
        if nx + i >= H:
            break
        if minDist[nx + i][ny] <= dist or A[nx + i][ny] == '@':
            break
        if minDist[nx + i][ny] > dist + 1:
            minDist[nx + i][ny] = dist + 1
            que.append((dist + 1, nx + i, ny))
    for i in range(1, K + 1):
        if nx - i < 0:
            break
        if minDist[nx - i][ny] <= dist or A[nx - i][ny] == '@':
            break
        if minDist[nx - i][ny] > dist + 1:
            minDist[nx - i][ny] = dist + 1
            que.append((dist + 1, nx - i, ny))
    for i in range(1, K + 1):
        if ny + i >= W:
            break
        if minDist[nx][ny + i] <= dist or A[nx][ny + i] == '@':
            break
        if minDist[nx][ny + i] > dist + 1:
            minDist[nx][ny + i] = dist + 1
            que.append((dist + 1, nx, ny + i))
    for i in range(1, K + 1):
        if ny - i < 0:
            break
        if minDist[nx][ny - i] <= dist or A[nx][ny - i] == '@':
            break
        if minDist[nx][ny - i] > dist + 1:
            minDist[nx][ny - i] = dist + 1
            que.append((dist + 1, nx, ny - i))

ans = minDist[tx][ty]
print(ans if ans < INF else -1)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    x1,y1,x2,y2 = map(int,ipt().split())
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    ms = [input()+"@" for _ in range(h)]
    ms.append("@"*(w+1))
    hq = []
    al = [[10**18]*w for _ in range(h)]
    al[x1][y1] = 0
    dr = [(0,1),(1,0),(0,-1),(-1,0)]
    hpq.heappush(hq,(0,x1,y1))
    while hq:
        c,x,y = hpq.heappop(hq)
        cn = c+1
        if x == x2 and y == y2:
            print(c)
            exit()
        for dx,dy in dr:
            xx = x
            yy = y
            for i in range(k):
                xx += dx
                yy += dy
                if ms[xx][yy] == "." and al[xx][yy] > cn:
                    al[xx][yy] = cn
                    hpq.heappush(hq,(cn,xx,yy))
                elif ms[xx][yy] == "." and al[xx][yy] == cn:
                    continue
                else:
                    break
    print(-1)

    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
sx, sy, tx, ty = map(lambda a: int(a) - 1, input().split())
INF = 10**18

A = [input() for _ in range(H)]

minDist = [[INF] * W for _ in range(H)]
minDist[sx][sy] = 0
que = deque([(0, sx, sy)])

while que:
    dist, nx, ny = que.popleft()

    for i in range(1, K + 1):
        if nx + i >= H:
            break
        if minDist[nx + i][ny] <= dist or A[nx + i][ny] == '@':
            break
        if minDist[nx + i][ny] > dist + 1:
            minDist[nx + i][ny] = dist + 1
            que.append((dist + 1, nx + i, ny))
    for i in range(1, K + 1):
        if nx - i < 0:
            break
        if minDist[nx - i][ny] <= dist or A[nx - i][ny] == '@':
            break
        if minDist[nx - i][ny] > dist + 1:
            minDist[nx - i][ny] = dist + 1
            que.append((dist + 1, nx - i, ny))
    for i in range(1, K + 1):
        if ny + i >= W:
            break
        if minDist[nx][ny + i] <= dist or A[nx][ny + i] == '@':
            break
        if minDist[nx][ny + i] > dist + 1:
            minDist[nx][ny + i] = dist + 1
            que.append((dist + 1, nx, ny + i))
    for i in range(1, K + 1):
        if ny - i < 0:
            break
        if minDist[nx][ny - i] <= dist or A[nx][ny - i] == '@':
            break
        if minDist[nx][ny - i] > dist + 1:
            minDist[nx][ny - i] = dist + 1
            que.append((dist + 1, nx, ny - i))

ans = minDist[tx][ty]
print(ans if ans < INF else -1)

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
sx, sy, tx, ty = map(lambda a: int(a) - 1, input().split())
INF = 10**18

A = [input() for _ in range(H)]

minDist = [[INF] * W for _ in range(H)]
minDist[sx][sy] = 0
que = deque([(0, sx, sy)])

while que:
    dist, nx, ny = que.popleft()

    for i in range(1, K + 1):
        if nx + i >= H:
            break
        if minDist[nx + i][ny] <= dist or A[nx + i][ny] == '@':
            break
        if minDist[nx + i][ny] > dist + 1:
            minDist[nx + i][ny] = dist + 1
            que.append((dist + 1, nx + i, ny))
    for i in range(1, K + 1):
        if nx - i < 0:
            break
        if minDist[nx - i][ny] <= dist or A[nx - i][ny] == '@':
            break
        if minDist[nx - i][ny] > dist + 1:
            minDist[nx - i][ny] = dist + 1
            que.append((dist + 1, nx - i, ny))
    for i in range(1, K + 1):
        if ny + i >= W:
            break
        if minDist[nx][ny + i] <= dist or A[nx][ny + i] == '@':
            break
        if minDist[nx][ny + i] > dist + 1:
            minDist[nx][ny + i] = dist + 1
            que.append((dist + 1, nx, ny + i))
    for i in range(1, K + 1):
        if ny - i < 0:
            break
        if minDist[nx][ny - i] <= dist or A[nx][ny - i] == '@':
            break
        if minDist[nx][ny - i] > dist + 1:
            minDist[nx][ny - i] = dist + 1
            que.append((dist + 1, nx, ny - i))

ans = minDist[tx][ty]
print(ans if ans < INF else -1)

Solution (Python):
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

Solution (Python):
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

Solution (Python):
h,w,k=map(int,input().split())
r,s,t,u=map(lambda x:int(x)-1,input().split())
b=[input()for _ in range(h)]
l=[[-1]*w for _ in range(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(print(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
print(-1)

Solution (Python):
h,w,k=map(int,input().split())
r,s,t,u=map(lambda x:int(x)-1,input().split())
b=[input()for _ in range(h)]
l=[[-1]*w for _ in range(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(print(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@":break
      if 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
print(-1)

Solution (Python):
h,w,k=map(int,input().split())
r,s,t,u=map(lambda x:int(x)-1,input().split())
b=[input()for _ in range(h)]
l=[[-1]*w for _ in range(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(print(l[x][y]))
  for e,f in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      p,q=x+e*i,y+f*i
      if not(0<=p<h and 0<=q<w)or b[p][q]=="@":break
      if 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)]
      l[p][q]=l[x][y]+1
print(-1)

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
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub+=[[x,y+j,d]]
                cand.add((x,y+j))
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub+=[[x,y-j,d]]
                cand.add((x,y-j))
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub+=[[x+j,y,d]]
                cand.add((x+j,y))
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub+=[[x-j,y,d]]
                cand.add((x-j,y))
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now+=[i]
    if l!=0:bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

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
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 = [[-1] * 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 0 <= dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == -1:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break

    print(-1)


if __name__ == '__main__':
    main()