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
import numpy as np
from heapq import heappop, heappush

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(C, H, W, S, T, K):
    INF = 10**18
    N = H * W
    q = [5 * S]
    dist = np.full((5 * N), INF, np.int64)
    dist[5 * S] = 0
    move = [0, 1, -1, W, -W]
    B = 5 * N + 10
    while q:
        x = heappop(q)
        dist_x, x = divmod(x, B)
        if dist_x > dist[x]:
            continue
        v, d = divmod(x, 5)
        if d == 0:
            
            for i in range(1, 5):
                w = v + move[i]
                y = 5 * w + i
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
        else:
            
            if dist_x % K != 0:
                w = v + move[d]
                y = 5 * w + d
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
            
            y = 5 * v
            dist_y = dist_x + (-dist_x) % K
            if dist_y < dist[y]:
                dist[y] = dist_y
                heappush(q, B * dist_y + y)
    x = dist[5 * T]
    if x == INF:
        return -1
    return dist[5 * T] // K

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(b1[:],i8,i8,i8,i8,i8)')(main)
    cc.compile()
    exit()
from my_module import main

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

C = np.zeros((H + 2, W + 2), np.bool_)
C[1:-1, 1:-1] = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'.'
C = C.ravel()
H += 2
W += 2

S = W * x1 + y1
T = W * x2 + y2

print(main(C, H, W, S, T, K))

Solution (Python):
from collections import deque

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

C = [list(input()) for _ in range(h)]

dist = [[10 ** 10] * w for _ in range(h)]

dist[x1][y1] = 0
que = deque([])
que.append((x1, y1))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while que:
    a, b = que.popleft()
    d = dist[a][b]
    if a == x2 and b == y2:
        print(dist[x2][y2])
        exit()
    for i in range(4):
        cx = a + dx[i]
        cy = b + dy[i]
        if cx < 0 or cx >= h or cy < 0 or cy >= w:
            continue
        if C[cx][cy] == "@":
            continue
        for j in range(1, k + 1):
            nx = a + dx[i] * j
            ny = b + dy[i] * j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                break
            if C[nx][ny] == "@":
                break
            if dist[nx][ny] < d + 1:
                break
            if dist[nx][ny] == 10 ** 10:
                dist[nx][ny] = d + 1
                que.append((nx, ny))
print(-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):
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):
def main():
  
  from collections import deque
  import sys
  input=lambda :sys.stdin.readline().rstrip()

  

  
  
  
  if 'get_ipython' in globals(): 
    
    h, w, k = 3, 5, 2
    x1, y1, x2, y2 = 3, 2, 3, 4
    dist = ['.....', '.@..@', '..@..']

  else:
    
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    dist = [input() for _ in range(h)]

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

  ans = [[-1]*w for _ in range(h)]
  ans[x1][y1] = 0

  que = deque()
  que.append((x1, y1))
  direction = ((1, 0), (-1, 0), (0, -1), (0, 1))
  while que:
    x, y = que.popleft()

    if x == x2 and y == y2:
      exit(print(ans[x][y]))

    for dx, dy in direction:
      for i in range(1, k+1):
        kx = x + dx*i
        ky = y + dy*i

        if not(0 <= kx < h and 0 <= ky < w) or dist[kx][ky] == "@":
          break

        if 0 <= ans[kx][ky] <= ans[x][y]:
          break

        if ans[kx][ky] == -1:
          que.append((kx, ky))

        ans[kx][ky] = ans[x][y]+1

  print(-1)

main()

Solution (Python):
from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]

q = deque()
for d in range(4):
    path[x1][y1][d] = (1, 0)
    q.append((x1, y1, d, 1, 0))

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while q:
    x, y, d, s, k = q.popleft()
    for nd in range(4):
        if nd == d:
            dx, dy = D[nd]
            nk = 1 if k == K else k + 1
            ns = s + 1 if k == K else s
        else:
            dx, dy = 0, 0
            nk = 0
            ns = s + 1
        nx = x + dx; ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
            path[nx][ny][nd] = (ns, nk)
            if ns == s:
                q.appendleft((nx, ny, nd, ns, nk))
            else:
                q.append((nx, ny, nd, ns, nk))

ans = INF
for d in range(4):
    ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans
print(ans)

Solution (Python):
from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]

q = deque()
for d in range(4):
    path[x1][y1][d] = (1, 0)
    q.append((x1, y1, d, 1, 0))

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while q:
    x, y, d, s, k = q.popleft()
    if k == K:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
                nk = 1
            else:
                dx, dy = 0, 0
                nk = 0
            nx = x + dx; ny = y + dy
            ns = s + 1
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                q.append((nx, ny, nd, ns, nk))
    else:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
                nk = k + 1
            else:
                dx, dy = 0, 0
                nk = 0
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                if ns == s:
                    q.appendleft((nx, ny, nd, ns, nk))
                else:
                    q.append((nx, ny, nd, ns, nk))

ans = INF
for d in range(4):
    ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans
print(ans)

Solution (Python):


import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    mas=[list(input()) for i in range(H)]

    dist=[[-1]*W for i in range(H)]
    dist[x1][y1]=0
    
    qu=deque([(x1,y1)])
    qup=qu.popleft
    qua=qu.append
    
    d=((-1,0),(1,0),(0,-1),(0,1))
    
    while(len(qu)>0):
        v=qup()
        for di in d:
            for i in range(1,K+1):
                nvh=v[0]+i*di[0]
                nvw=v[1]+i*di[1]
                if nvh<0 or nvh>=H or nvw<0 or nvw>=W or mas[nvh][nvw]=="@":
                    break
                if dist[nvh][nvw]!=-1 and dist[nvh][nvw]<=dist[v[0]][v[1]]:
                    break
                if dist[nvh][nvw]==-1:
                    dist[nvh][nvw]=dist[v[0]][v[1]]+1
                    qua((nvh,nvw))
    print(dist[x2][y2])
    
if __name__=="__main__":
    main()

Solution (Python):
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 = [[-1] * w for _ in range(h)]
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '.':
            m[hh][ww] = h*w

from collections import deque
q = deque()

q.append((0, x1, y1))
while q:
    s, x, y = q.popleft()
    s1 = s + 1

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

print(-1)

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

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

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

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

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

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

dist = [input() for _ in range(h)]
ans = [[-1]*w for _ in range(h)]
ans[x1][y1] = 0

que = deque()
que.append((x1, y1))
direction = ((1, 0), (-1, 0), (0, -1), (0, 1))
while que:
  x, y = que.popleft()

  if x == x2 and y == y2:
      print(ans[x][y])
      exit()

  for dx, dy in direction:
    for i in range(1, k+1):
      kx = x + dx*i
      ky = y + dy*i

      if not(0 <= kx < h and 0 <= ky < w) or dist[kx][ky] == "@":
          break

      if 0 <= ans[kx][ky] <= ans[x][y]:
          break

      if ans[kx][ky] == -1:
          que.append((kx, ky))

      ans[kx][ky] = ans[x][y]+1

print(-1)

Solution (Python):
from collections import deque

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

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

ans_array = [-1] * (H * W * 4)

pos = deque()

start_pos = ((x1 - 1) * W + (y1 - 1)) * 4
goal_pos = ((x2 - 1) * W + (y2 - 1)) * 4

for i in range(4):
    pos.append(start_pos + i)
    ans_array[start_pos + i] = 0

while(len(pos)):
    now_pos = pos.popleft()
    d = now_pos % 4
    h = (now_pos - d) // (4 * W) + 1
    w = ((now_pos - d) // 4) % W + 1
    
    if d == 0:
        for i in range(1, K + 1):
            if h + i > H or c_array[h + i - 1][w - 1] == '@':
                break
            newpos_array = [((h + i - 1) * W + (w - 1)) * 4 + 1, ((h + i - 1)
                                                                  * W + (w - 1)) * 4 + 3, ((h + i - 1) * W + (w - 1)) * 4 + 0, ((h + i - 1) * W + (w - 1)) * 4 + 2]
            for n, newpos in enumerate(newpos_array):
                if newpos >= goal_pos and newpos < goal_pos + 4:
                    print(ans_array[now_pos] + 1)
                    exit()
                if ans_array[newpos] == -1:
                    ans_array[newpos] = ans_array[now_pos] + 1
                    if n < 2 or (n == 2 and i == K):
                        pos.append(newpos)
    if d == 1:
        for i in range(1, K + 1):
            if w + i > W or c_array[h - 1][w + i - 1] == '@':
                break
            newpos_array = [((h - 1) * W + (w + i - 1)) * 4 + 0, ((h - 1) *
                                                                  W + (w + i - 1)) * 4 + 2, ((h - 1) * W + (w + i - 1)) * 4 + 1, ((h - 1) * W + (w + i - 1)) * 4 + 3]
            for n, newpos in enumerate(newpos_array):
                if newpos >= goal_pos and newpos < goal_pos + 4:
                    print(ans_array[now_pos] + 1)
                    exit()
                if ans_array[newpos] == -1:
                    ans_array[newpos] = ans_array[now_pos] + 1
                    if n < 2 or (n == 2 and i == K):
                        pos.append(newpos)
    if d == 2:
        for i in range(1, K + 1):
            if h - i < 1 or c_array[h - i - 1][w - 1] == '@':
                break
            newpos_array = [((h - i - 1) * W + (w - 1)) * 4 + 1, ((h - i - 1)
                                                                  * W + (w - 1)) * 4 + 3, ((h - i - 1) * W + (w - 1)) * 4 + 2, ((h - i - 1) * W + (w - 1)) * 4 + 0]
            for n, newpos in enumerate(newpos_array):
                if newpos >= goal_pos and newpos < goal_pos + 4:
                    print(ans_array[now_pos] + 1)
                    exit()
                if ans_array[newpos] == -1:
                    ans_array[newpos] = ans_array[now_pos] + 1
                    if n < 2 or (n == 2 and i == K):
                        pos.append(newpos)
    if d == 3:
        for i in range(1, K + 1):
            if w - i < 1 or c_array[h - 1][w - i - 1] == '@':
                break
            newpos_array = [((h - 1) * W + (w - i - 1)) * 4 + 0, ((h - 1) *
                                                                  W + (w - i - 1)) * 4 + 2, ((h - 1) * W + (w - i - 1)) * 4 + 3, ((h - 1) * W + (w - i - 1)) * 4 + 1]
            for n, newpos in enumerate(newpos_array):
                if newpos >= goal_pos and newpos < goal_pos + 4:
                    print(ans_array[now_pos] + 1)
                    exit()
                if ans_array[newpos] == -1:
                    ans_array[newpos] = ans_array[now_pos] + 1
                    if n < 2 or (n == 2 and i == K):
                        pos.append(newpos)
print(-1)

Solution (Python):
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

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

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

dd = [(1,0),(-1,0),(0,1),(0,-1)]

def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    while q:
      y,x = q.popleft()
      if (y,x) == (s,t):
          print(d[s][t])
          return
      nd = d[y][x] + 1
      for dy,dx in dd:
          ny,nx = y,x
          for _ in range(k):
              ny += dy
              nx += dx
              if 0 <= ny < h and 0 <= nx < w and c[ny][nx] != "@" and nd <= d[ny][nx]:
                  if nd < d[ny][nx]:
                      d[ny][nx] = nd
                      q.append((ny,nx))
                  continue
              break
    print(-1)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)

INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  
  
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: 
        break
      if reach[x][y]+1 < reach[nx][ny]:
        reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
        Q.append((nx,ny))
      if nx == gx and ny == gy:
        
        print(reach[nx][ny])
        exit()
print(-1)

Solution (Python):


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

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = set([(x1-1,y1-1)])
step = 1

while len(que)>0:
  que_next = set()
  for q in que:
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      que_next.add((x-i,y))
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      que_next.add((x+i,y))
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      que_next.add((x,y-i))
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      que_next.add((x,y+i))
  que = que_next
  for q in que:
    if q[0]==x2-1 and q[1]==y2-1:
      print(step)
      exit()
    T[q[0]][q[1]] = 1
  step += 1

print(-1)

Solution (Python):


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

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = set([(x1-1,y1-1)])
step = 1

while len(que)>0:
  que_next = set()
  for q in que:
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next.add((x-i,y))
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next.add((x+i,y))
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next.add((x,y-i))
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next.add((x,y+i))
  que = que_next
  for q in que:
    T[q[0]][q[1]] = 1
  step += 1

print(-1)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(si, sj)])
    while queue:
        i, j = queue.popleft()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                if dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q0 = deque([(0,x1,y1,(0,0),0)])
q1 = deque()

dx = [0,1,0,-1]
dy = [1,0,-1,0]

dist = [None]*(w*h)
dist[x1*w+y1] = 0

done = [0]*(w*h)
done[x1*w+y1] = 15

while q0 or q1:
    if not q0:
        q0 = q1
        q1 = deque()
    d, x, y, t, td = q0.popleft()
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
            q = q0
        else:
            nd = d+1
            ntd = 1
            q = q1
        if dist[nx*w+ny] is None or nd<dist[nx*w+ny]:
            q.append((nd,nx,ny,(xx,yy),ntd))
            dist[nx*w+ny] = nd
            done[nx*w+ny] = 1<<(i)
        elif nd==dist[nx*w+ny]and ((done[nx*w+ny]&1<<(i))==0):
            q.append((nd,nx,ny,(xx,yy),ntd))
            done[nx*w+ny] |= 1<<(i)
            
if dist[x2*w+y2] is None:
    print(-1)
else:
    print(dist[x2*w+y2])

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      if dp[pp * W + q] != inf: continue
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      if dp[pp * W + q] != inf: continue
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      if dp[p * W + qq] != inf: continue
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      if dp[p * W + qq] != inf: continue
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)

Solution (Python):
import sys
from collections import deque


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