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
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)
    if l==0:
        return
    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.append([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.append([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.append([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.append([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.append(i)
    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():
    import sys
    read = sys.stdin.read
    readline = sys.stdin.readline
    readlines = sys.stdin.readlines
    from collections import deque

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

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
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)

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()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0

def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    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.append([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.append([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.append([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.append([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.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

Solution (Python):
from collections import deque
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy]+1):
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])
 
 
if __name__ == "__main__":
    main()

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

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

    
    
    

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            

            
            

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()

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

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

    
    
    

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            

            
            

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) 

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) 
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                if dist[nx][ny] <= dist[x][y]:
                    break 
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                    dist[nx][ny] = dist[x][y] + 1
print(-1)

Solution (Python):
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) 

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) 
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                if dist[nx][ny] <= dist[x][y]:
                    break 
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                    dist[nx][ny] = dist[x][y] + 1
print(-1)

Solution (Python):
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) 

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) 
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                
                
                if dist[nx][ny] <= dist[x][y]:
                    break 
                
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
print(-1)

Solution (Python):
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  d=[]
  d.append((sx,sy))
  for ss in d:
    x,y=ss
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      if b[x+i][y]==0:d.append((x+i,y))
      b[x+i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      if b[x-i][y]==0:d.append((x-i,y))
      b[x-i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      if b[x][y+j]==0:d.append((x,y+j))
      b[x][y+j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      if b[x][y-j]==0:d.append((x,y-j))
      b[x][y-j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  d=[]
  d.append((sx,sy))
  for ss in d:
    x,y=ss
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      if b[x+i][y]==0:d.append((x+i,y))
      b[x+i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      if b[x-i][y]==0:d.append((x-i,y))
      b[x-i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      if b[x][y+j]==0:d.append((x,y+j))
      b[x][y+j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      if b[x][y-j]==0:d.append((x,y-j))
      b[x][y-j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Solution (Python):
import sys
input=sys.stdin.readline
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)

Solution (Python):
import sys
input=sys.stdin.readline
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)

Solution (Python):
import sys
input=sys.stdin.readline
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)

Solution (Python):
from heapq import heappop, heappush

import numpy as np

from numba import njit


@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)', cache=True)
def reachable(field, h2, w2, k):
    
    hw = h2 * w2
    up = np.full(hw, -1, dtype=np.int64)
    dw = np.full(hw, -1, dtype=np.int64)
    lf = np.full(hw, -1, dtype=np.int64)
    rg = np.full(hw, -1, dtype=np.int64)
    lf_tmp = -1
    for i in range(w2, hw - w2):
        if field[i]:
            if lf_tmp == -1:
                lf_tmp = i
            lf[i] = max(lf_tmp, i - k)
        else:
            lf_tmp = -1
    rg_tmp = -1
    for i in range(hw - w2, w2 - 1, -1):
        if field[i]:
            if rg_tmp == -1:
                rg_tmp = i
            rg[i] = min(rg_tmp, i + k)
        else:
            rg_tmp = -1
    wk = w2 * k
    for j in range(1, w2):
        up_tmp = -1
        for i in range(j, hw, w2):
            if field[i]:
                if up_tmp == -1:
                    up_tmp = i
                up[i] = max(up_tmp, i - wk)
            else:
                up_tmp = -1
        dw_tmp = 0
        for i in range(hw - w2 + j, w2 - 1, -w2):
            if field[i]:
                if dw_tmp == -1:
                    dw_tmp = i
                dw[i] = min(dw_tmp, i + wk)
            else:
                dw_tmp = -1
    return up, dw, lf, rg


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)', cache=True)
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0

    q = [(0, s)]
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        nc = cost + 1

        for u in range(up[v], v, w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(dw[v], v, -w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(lf[v], v, 1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Solution (Python):
from heapq import heappop, heappush

import numpy as np

from numba import njit


@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)')
def reachable(field, h2, w2, k):
    
    hw = h2 * w2
    up = np.full(hw, -1, dtype=np.int64)
    dw = np.full(hw, -1, dtype=np.int64)
    lf = np.full(hw, -1, dtype=np.int64)
    rg = np.full(hw, -1, dtype=np.int64)
    lf_tmp = -1
    for i in range(w2, hw - w2):
        if field[i]:
            if lf_tmp == -1:
                lf_tmp = i
            lf[i] = max(lf_tmp, i - k)
        else:
            lf_tmp = -1
    rg_tmp = -1
    for i in range(hw - w2, w2 - 1, -1):
        if field[i]:
            if rg_tmp == -1:
                rg_tmp = i
            rg[i] = min(rg_tmp, i + k)
        else:
            rg_tmp = -1
    wk = w2 * k
    for j in range(1, w2):
        up_tmp = -1
        for i in range(j, hw, w2):
            if field[i]:
                if up_tmp == -1:
                    up_tmp = i
                up[i] = max(up_tmp, i - wk)
            else:
                up_tmp = -1
        dw_tmp = 0
        for i in range(hw - w2 + j, w2 - 1, -w2):
            if field[i]:
                if dw_tmp == -1:
                    dw_tmp = i
                dw[i] = min(dw_tmp, i + wk)
            else:
                dw_tmp = -1
    return up, dw, lf, rg


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)')
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0

    q = [(0, s)]
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        nc = cost + 1

        for u in range(up[v], v, w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(dw[v], v, -w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(lf[v], v, 1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Solution (Python):
from collections import deque
from heapq import heappop, heappush

import numpy as np

from numba import njit


@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)')
def reachable(field, h2, w2, k):
    
    hw = h2 * w2
    up = np.full(hw, -1, dtype=np.int64)
    dw = np.full(hw, -1, dtype=np.int64)
    lf = np.full(hw, -1, dtype=np.int64)
    rg = np.full(hw, -1, dtype=np.int64)
    lf_tmp = -1
    for i in range(w2, hw - w2):
        if field[i]:
            if lf_tmp == -1:
                lf_tmp = i
            lf[i] = max(lf_tmp, i - k)
        else:
            lf_tmp = -1
    rg_tmp = -1
    for i in range(hw - w2, w2 - 1, -1):
        if field[i]:
            if rg_tmp == -1:
                rg_tmp = i
            rg[i] = min(rg_tmp, i + k)
        else:
            rg_tmp = -1
    wk = w2 * k
    for j in range(1, w2):
        up_tmp = -1
        for i in range(j, hw, w2):
            if field[i]:
                if up_tmp == -1:
                    up_tmp = i
                up[i] = max(up_tmp, i - wk)
            else:
                up_tmp = -1
        dw_tmp = 0
        for i in range(hw - w2 + j, w2 - 1, -w2):
            if field[i]:
                if dw_tmp == -1:
                    dw_tmp = i
                dw[i] = min(dw_tmp, i + wk)
            else:
                dw_tmp = -1
    return up, dw, lf, rg


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)')
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0

    q = [(0, s)]
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        nc = cost + 1

        for u in range(up[v], v, w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(dw[v], v, -w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(lf[v], v, 1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

h, w, K = na()
x1, y1, x2, y2 = na()
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

bd = [ns() for _ in range(h)]

q = deque()
ds = [9999999999999999] * (h*w)

q.append((x1, y1))
ds[x1*w+y1] = 0
dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)
while len(q) > 0:
    r, c = q.popleft()
    for i in range(4):
        for j in range(1, K+1):
            nr, nc = r + dr[i] * j, c + dc[i] * j
            if 0 <= nr < h and 0 <= nc < w and bd[nr][nc] != "@":
                nd = ds[r*w+c] + 1
                if nd < ds[nr*w+nc]:
                    ds[nr*w+nc] = nd
                    q.append((nr, nc))
                elif nd <= ds[nr*w+nc]:
                    continue
                else:
                    break
            else:
                break
ans = ds[x2*w+y2]
if ans < 999999999999:
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    X1, Y1, X2, Y2 = [int(x) for x in input().split()]
    C = [input().strip() for _ in range(H)]

    q = collections.deque()
    q.append((X1 - 1, Y1 - 1, 0))

    V = [[float("inf")] * W for j in range(H)]
    V[X1 - 1][Y1 - 1] = 0


    while q:
        c = q.popleft()
        x = c[0]
        y = c[1]
        d = c[2]

        if y == Y2 - 1 and x == X2 - 1:
            print(c[2])
            return

        e, w, n, s = True, True, True, True
        for k in range(1, K + 1):
            if not e and not w and not n and not s:
                break
            if e:
                if y + k >= W or C[x][y + k] == "@":
                    e = False
                else:
                    if V[x][y + k] == float("inf"):
                        V[x][y + k] = d + 1
                        q.append((x, y + k, d + 1))

                    if V[x][y + k] < d + 1:
                        e = False
            if w:
                if y - k < 0 or C[x][y - k] == "@":
                    w = False
                else:
                    if V[x][y - k] == float("inf"):
                        V[x][y - k] = d + 1
                        q.append((x, y - k, d + 1))
                    if V[x][y - k] < d + 1:
                        w = False

            if n:
                if x - k < 0 or C[x - k][y] == "@":
                    n = False
                else:
                    if V[x - k][y] == float("inf"):
                        V[x - k][y] = d + 1
                        q.append((x - k, y, d + 1))
                    if V[x - k][y] < d + 1:
                        n = False

            if s:
                if x + k >= H or C[x + k][y] == "@":
                    s = False
                else:
                    if V[x + k][y] == float("inf"):
                        V[x + k][y] = d + 1
                        q.append((x + k, y, d + 1))
                    if V[x + k][y] < d + 1:
                        s = False

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
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)

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    X1, Y1, X2, Y2 = [int(x) for x in input().split()]
    C = [input().strip() for _ in range(H)]

    q = collections.deque()
    q.append((X1 - 1, Y1 - 1, 0))

    V = [[float("inf")] * W for j in range(H)]
    V[X1 - 1][Y1 - 1] = 0


    while q:
        c = q.popleft()
        x = c[0]
        y = c[1]
        d = c[2]

        if y == Y2 - 1 and x == X2 - 1:
            print(c[2])
            return

        e, w, n, s = True, True, True, True
        for k in range(1, K + 1):
            if not e and not w and not n and not s:
                break
            if e:
                if y + k >= W or C[x][y + k] == "@":
                    e = False
                else:
                    if V[x][y + k] == float("inf"):
                        V[x][y + k] = d + 1
                        q.append((x, y + k, d + 1))

                    if V[x][y + k] < d + 1:
                        e = False
            if w:
                if y - k < 0 or C[x][y - k] == "@":
                    w = False
                else:
                    if V[x][y - k] == float("inf"):
                        V[x][y - k] = d + 1
                        q.append((x, y - k, d + 1))
                    if V[x][y - k] < d + 1:
                        w = False

            if n:
                if x - k < 0 or C[x - k][y] == "@":
                    n = False
                else:
                    if V[x - k][y] == float("inf"):
                        V[x - k][y] = d + 1
                        q.append((x - k, y, d + 1))
                    if V[x - k][y] < d + 1:
                        n = False

            if s:
                if x + k >= H or C[x + k][y] == "@":
                    s = False
                else:
                    if V[x + k][y] == float("inf"):
                        V[x + k][y] = d + 1
                        q.append((x + k, y, d + 1))
                    if V[x + k][y] < d + 1:
                        s = False

    print(-1)


if __name__ == '__main__':
    main()