Problem:
 Score : 600 points    Problem Statement Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i -th row from the north and j -th column from the west.  Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @ , and it does not if c_{ij} is . .  In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.  Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2) .
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.      Constraints  1 \leq H,W,K \leq 10^6  H \times W \leq 10^6  1 \leq x_1,x_2 \leq H  1 \leq y_1,y_2 \leq W  x_1 \neq x_2 or y_1 \neq y_2 .  c_{i,j} is . or @ .  c_{x_1,y_1} =  .  c_{x_2,y_2} =  .  All numbers in input are integers.         Input Input is given from Standard Input in the following format:  H  W  K  x_1  y_1  x_2  y_2  c_{1,1}c_{1,2}  ..  c_{1,W}  c_{2,1}c_{2,2}  ..  c_{2,W}  :  c_{H,1}c_{H,2}  ..  c_{H,W}       Output Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2) , or print -1 if the travel is impossible.        Sample Input 1 3 5 2
3 2 3 4
.....
.@..@
..@..      Sample Output 1 5  Initially, Snuke is at the square (3,2) .
He can reach the square (3, 4) by making five strokes as follows:    From (3, 2) , go west one square to (3, 1) .    From (3, 1) , go north two squares to (1, 1) .    From (1, 1) , go east two squares to (1, 3) .    From (1, 3) , go east one square to (1, 4) .    From (1, 4) , go south two squares to (3, 4) .         Sample Input 2 1 6 4
1 1 1 6
......      Sample Output 2 2       Sample Input 3 3 3 1
2 1 2 3
.@.
.@.
.@.      Sample Output 3 -1

Solution (Python):
from heapq import heappop, heappush 
from collections import deque
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    
    inf = 1e18
    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(0, xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        cost, x, y = que.popleft()
        if cost > dist[x][y]:
            continue
        for v in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[v]
                ny += dy[v]
                if not field[nx][ny]:
                    break
                if dist[nx][ny]<=dist[x][y]:
                    break
                if dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    que.append((dist[nx][ny], nx, ny))

    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])

        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    for i in range(h):
        
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    h += 2
    w += 2
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

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

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            elif dp[x+dx*j][y+dy*j]==dp[x][y]+1:continue
            elif dp[x+dx*j][y+dy*j]<=dp[x][y]:break
    
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)

Solution (Python):
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

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

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

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()

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

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

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        m,x,y =  heapq.heappop(q)
        if d[x][y] < m: continue
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < m + 1: break
                if d[nx][ny] == m + 1: continue
                d[nx][ny] = m + 1
                q.append((m+1,nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        m,x,y =  heapq.heappop(q)
        if d[x][y] < m: continue
        d[x][y] = m
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < m + 1: break
                if d[nx][ny] == m + 1: continue
                d[nx][ny] = m + 1
                q.append((m+1,nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        n,x,y =  heapq.heappop(q)
        if d[x][y] < n: continue
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((d[nx][ny],nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    from collections import deque
    
    H,W,K=MI()
    x1,y1,x2,y2=MI()
    
    C=[]
    C.append(["@"]*(W+2))
    for _ in range(H):
        c=["@"] + list(input()) + ["@"]
        C.append(c)
    C.append(["@"]*(W+2))
    
    
    inf=10**10
    D=[[[(inf,inf)]*4 for _ in range(W+2)]for _ in range(H+2)]
    
    
    
    dq=deque()
    for k in range(4):
        D[x1][y1][k]=(0,0)
        dq.append((x1,y1,k,0,0))
    
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    
    
    
    
    while len(dq):
        x,y,d,cnt,k=dq.popleft()
        
        for nd in range(4):
            
            if nd==d:
                nx=x+dx[nd]
                ny=y+dy[nd]
                nk=(k+1)%K
                ncnt=cnt
                if k+1>=K:
                    ncnt+=1
            
            else:
                nk=0
                ncnt=cnt
                if k!=0:
                    ncnt+=1
                nx=x
                ny=y
            if C[nx][ny]==".":
                if D[nx][ny][nd] > (ncnt,nk):
                    D[nx][ny][nd]=(ncnt,nk)
                    if ncnt==cnt:
                        dq.appendleft((nx,ny,nd,ncnt,nk))
                    else:
                        dq.append((nx,ny,nd,ncnt,nk))
                    
    ans=inf
    for d in range(4):
        temp=D[x2][y2][d][0]
        if D[x2][y2][d][1]:
            temp+=1
        ans=min(ans,temp)
        
    if ans>=inf:
        ans=-1
    print(ans)
    
    
    
    
    
    
    
    
    
    
    
        
    
                    
            

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

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


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


while q:
    x, y, d, c, k = q.popleft()

    
    
    
    
    for nd in range(4):
        if nd == d:
            dx, dy = D[nd]
            nk = 1 if k == K else k + 1
            nc = c + 1 if k == K else c
        else:
            dx, dy = 0, 0
            nk = 0
            nc = c + 1
        nx = x + dx; ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (nc, nk):
            path[nx][ny][nd] = (nc, nk)
            if nc == c:
                q.appendleft((nx, ny, nd, nc, nk))
            else:
                q.append((nx, ny, nd, nc, 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
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, K = mapint()
y1, x1, y2, x2 = mapint()
pond = [list(input()) for _ in range(H)]
from collections import deque
Q = deque([(y1-1, x1-1)])

inf = 10**18
dist = [[inf]*W for _ in range(H)]
dist[y1-1][x1-1] = 0
while Q:
    y, x = Q.popleft()
    if y==y2-1 and x==x2-1:
        break
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for i in range(1, K+1):
            ny, nx = y+dy*i, x+dx*i
            if ny<0 or ny>=H or nx<0 or nx>=W:
                break
            if pond[ny][nx]=='@':
                break
            if dist[ny][nx]<=dist[y][x]:
                break
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))
if dist[y2-1][x2-1]>=10**17:
    print(-1)
else:
    print(dist[y2-1][x2-1])

Solution (Python):
import collections

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

ans = [[float("inf")] * W for j in range(H)]

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

ans[X1 - 1][Y1 - 1] = 0

while q:
    cx, cy = q.popleft()
    cc = ans[cx][cy]
    nc = cc + 1

    
    for i in range(1, K + 1):
        if cy + i >= W or C[cx][cy + i] == "@":
            break
        if ans[cx][cy + i] <= nc - 1:
            break
        if ans[cx][cy + i] <= nc:
            continue
        ans[cx][cy + i] = nc
        q.append((cx, cy + i))
    
    for i in range(1, K + 1):
        if cy - i <= -1 or C[cx][cy - i] == "@":
            break
        if ans[cx][cy - i] <= nc - 1:
            break
        if ans[cx][cy - i] <= nc:
            continue
        ans[cx][cy - i] = nc
        q.append((cx, cy - i))
    
    for i in range(1, K + 1):
        if cx - i <= -1 or C[cx - i][cy] == "@":
            break
        if ans[cx - i][cy] <= nc - 1:
            break
        if ans[cx - i][cy] <= nc:
            continue
        ans[cx - i][cy] = nc
        q.append((cx - i, cy))
    
    for i in range(1, K + 1):
        if cx + i >= H or C[cx + i][cy] == "@":
            break
        if ans[cx + i][cy] <= nc - 1:
            break
        if ans[cx + i][cy] <= nc:
            continue
        ans[cx + i][cy] = nc
        q.append((cx + i, cy))

if ans[X2 - 1][Y2 - 1] == float("inf"):
    print(-1)
else:
    print(ans[X2 - 1][Y2 - 1])

Solution (Python):

from collections import deque

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

    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    INF = 10**12
    
    for i in range(H):
        for j in range(W):
            if c[i][j] == '@': continue
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W and c[y][x] == '.':
                    adj[W*i+j].append(W*y+x)
    
    queue = deque([W*x1+y1])
    visit = [INF] * (W*H)
    visit[W*x1+y1] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            
            count = 0
            direct = u - now
            fromC = now
            toC = u
            while count < K and toC in adj[fromC] and visit[now] < visit[toC]:
                count += 1
                if visit[toC] == INF:
                    queue.append(toC)
                    visit[toC] = visit[now] + 1
                fromC = toC
                toC += direct 

    print(visit[W*x2+y2]) if visit[W*x2+y2] < INF else print(-1)
    

if __name__ == "__main__":
    main()

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 = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)

Q = deque([])
Q.append((sx,sy))
reach = [[INF]*W for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  nx,ny = Q.popleft()
  for i in range(4):
    tx,ty = nx,ny
    step = K
    while step > 0:
      tx += dxdy[i][0]
      ty += dxdy[i][1]
      
      if 0>tx or tx>=H or 0>ty or ty>=W or Pond[tx][ty] == "@": 
        
        break 
      
      if reach[nx][ny] + 1 > reach[tx][ty]: 
        
        break
      if reach[nx][ny] + 1 == reach[tx][ty]:
        
        step -=1
        continue
      reach[tx][ty] = reach[nx][ny] + 1
      Q.append((tx,ty))
      step -=1


ans = reach[gx][gy]
if ans == INF:
  print(-1)
else:
  print(ans)

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 = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)

Q = deque([])
Q.append((sx,sy))
reach = [[INF]*W for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  nx,ny = Q.popleft()
  step = K
  for i in range(4):
    for fac in range(1,K+1):
      tx = nx + fac*dxdy[i][0]
      ty = ny + fac*dxdy[i][1]
      
      if 0>tx or tx>=H or 0>ty or ty>=W or Pond[tx][ty] == "@": 
        
        break 
      
      if reach[nx][ny] + 1 > reach[tx][ty]: 
        
        break
      if reach[nx][ny] + 1 == reach[tx][ty]:
        
        continue
      reach[tx][ty] = reach[nx][ny] + 1
      Q.append((tx,ty))


ans = reach[gx][gy]
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):
h,w,k=map(int,input().split())

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

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

from collections import deque
stack=deque([(y1-1,x1-1)])

before=[[0]*w for _ in range(h)]
dic={}
dic[0]=0
dic[(0,1)]=(0,-1)
dic[(0,-1)]=(0,1)
dic[(1,0)]=(-1,0)
dic[(-1,0)]=(1,0)

maze[y1-1][x1-1]=0

while len(stack)>0:
    
    (y,x)=stack.popleft()
    if (y,x)==(y2-1,x2-1):
        print(maze[y][x])
        exit()

    
    for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
        
        flag=0
        if (my,mx)!=dic[before[y][x]]:
            for kk in range(1,k+1):
                ny=y+my*kk
                nx=x+mx*kk
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]!="@":
                        if maze[ny][nx]==".":
                            maze[ny][nx]=maze[y][x]+1
                            stack.append((ny,nx))
                            before[ny][nx]=((my,mx))
                        if maze[ny][nx]==maze[y][x]+1:
                            continue
                        else:
                            break
                    else:
                        break
                else:
                    break
    
print(-1)

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 = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)

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



print(-1)

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 = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)

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



print(-1)

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):
import sys
from collections import deque
input = sys.stdin.readline

def bfs(sl, visited, sy, sx, gy, gx, h, w, k):
    q = deque([ (sy,sx) ])
    visited[sy][sx] = 0
    while q:
        
        y, x = q.popleft()
        if [y, x] == [gy, gx]:
            return visited[gy][gx]
        for i in range(1,k+1):
            ny = y+i
            if ny >= h:
                break
            if sl[ny][x] == '@':
                break
            if 0 <= visited[ny][x] <= visited[y][x]:
                break
            if visited[ny][x] != visited[y][x]+1: 
                visited[ny][x] = visited[y][x]+1
                q.append((ny,x))

        for i in range(1,k+1):
            ny = y-i
            if ny < 0:
                break
            if sl[ny][x] == '@':
                break
            if 0 <= visited[ny][x] <= visited[y][x]:
                break
            if visited[ny][x] != visited[y][x]+1: 
                visited[ny][x] = visited[y][x]+1
                q.append((ny,x))

        for i in range(1,k+1):
            nx = x+i
            if nx >= w:
                break
            if sl[y][nx] == '@':
                break
            if 0 <= visited[y][nx] <= visited[y][x]:
                break
            if visited[y][nx] != visited[y][x]+1: 
                visited[y][nx] = visited[y][x]+1
                q.append((y,nx))

        for i in range(1,k+1):
            nx = x-i
            if nx < 0:
                break
            if sl[y][nx] == '@':
                break
            if 0 <= visited[y][nx] <= visited[y][x]:
                break
            if visited[y][nx] != visited[y][x]+1: 
                visited[y][nx] = visited[y][x]+1
                q.append((y,nx))

    return -1

def main():
    h,w,k = map(int, input().split())
    x1,y1,x2,y2 = map(int, input().split())
    cl = []
    for i in range(h):
        row = list(input())
        cl.append(row)

    visited = [ [-1]*w for i in range(h)]
    ans = bfs(cl, visited, x1-1,y1-1,x2-1,y2-1,h,w,k)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [list(input()) for i in range(h)]
visited = [[-1] * w for i in range(h)]
visited[x1 - 1][y1 - 1] = 0
Q = deque([(x1 - 1, y1 - 1)])
while Q:
    nx, ny = Q.popleft()
    if nx == x2 - 1 and ny == y2 - 1:
        exit(print(visited[nx][ny]))
    for dx, dy in d:
        for i in range(k):
            p, q = nx + dx * (i + 1), ny + dy * (i + 1)
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if 0 <= visited[p][q] <= visited[nx][ny]:
                break
            if visited[p][q] == -1:
                Q.append((p, q))
            visited[p][q] = visited[nx][ny] + 1
print(-1)

Solution (Python):
from collections import deque

def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    M = []
    Cost = [[1000000] * W for i in range(H)]
    dxdy = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    Cost[x1-1][y1-1] = 0
    q = deque([(x1-1, y1-1)])
    for h in range(H):
        M.append(list(input()))

    while q:
        x, y = q.popleft()
        for ddx, ddy in dxdy:
            for i in range(1, K+1):
                dx = ddx*i
                dy = ddy*i

                if not (0 <= x+dx < H and 0 <= y+dy < W):
                    break
                if M[x+dx][y+dy] == '@' or Cost[x+dx][y+dy] <= Cost[x][y]:
                    break
                if x+dx == x2-1 and y+dy == y2-1:
                    print(Cost[x][y]+1)
                    exit(0)
                if Cost[x+dx][y+dy] > Cost[x][y] + 1:
                    Cost[x+dx][y+dy] = Cost[x][y] + 1
                    q.append((x+dx,y+dy))
    

    print(-1)

    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[10**10]*(w+2) for i in range(h+2)]
V[sy][sx]=0
D=[[[0,0,0,0] for j in range(w+2)] for i in range(h+2)]
D[sy][sx]=[1,1,1,1]
X=deque([])
Y=deque([])
i=1
while G[sy-i][sx]==".":
  Y.append(sy-i)
  X.append(sx)
  V[sy-i][sx]=1
  D[sy-i][sx][0]=1
  D[sy-i][sx][1]=1
  if i==k:
    D[sy-i][sx][0]=0
    break
  i=i+1
i=1
while G[sy+i][sx]==".":
  Y.append(sy+i)
  X.append(sx)
  V[sy+i][sx]=1
  D[sy+i][sx][0]=1
  D[sy+i][sx][1]=1
  if i==k:
    D[sy+i][sx][1]=0
    break
  i=i+1

i=1
while G[sy][sx-i]==".":
  Y.append(sy)
  X.append(sx-i)
  V[sy][sx-i]=1
  D[sy][sx-i][2]=1
  D[sy][sx-i][3]=1
  if i==k:
    D[sy][sx-i][2]=0
    break
  i=i+1
i=1
while G[sy][sx+i]==".":
  Y.append(sy)
  X.append(sx+i)
  V[sy][sx+i]=1
  D[sy][sx+i][2]=1
  D[sy][sx+i][3]=1
  if i==k:
    D[sy][sx+i][3]=0
    break
  i=i+1

def yn(yy,xx):
  D[yy][xx][0]=1
  i=1
  while G[yy-i][xx]==".":
    if V[yy][xx]+1>V[yy-i][xx]:
      break
    D[yy-i][xx][0]=1
    D[yy-i][xx][1]=1
    V[yy-i][xx]=V[yy][xx]+1
    if i==k:
      D[yy-i][xx][0]=0
      Y.append(yy-i)
      X.append(xx)
      break

    Y.append(yy-i)
    X.append(xx)
    i=i+1


def yp(yy,xx):
  D[yy][xx][1]=1
  i=1
  while G[yy+i][xx]==".":
    if V[yy][xx]+1>V[yy+i][xx]:
      break
    D[yy+i][xx][0]=1
    D[yy+i][xx][1]=1
    V[yy+i][xx]=min(V[yy+i][xx],V[yy][xx]+1)
    if i==k:
      D[yy+i][xx][1]=0
      Y.append(yy+i)
      X.append(xx)
      break

    Y.append(yy+i)
    X.append(xx)
    i=i+1


def xn(yy,xx):
  D[yy][xx][2]=1
  i=1
  while G[yy][xx-i]==".":
    if V[yy][xx]+1>V[yy][xx-i]:
      break
    D[yy][xx-i][2]=1
    D[yy][xx-i][3]=1
    V[yy][xx-i]=min(V[yy][xx-i],V[yy][xx]+1)
    if i==k:
      D[yy][xx-i][2]=0
      Y.append(yy)
      X.append(xx-i)
      break

    Y.append(yy)
    X.append(xx-i)
    i=i+1


def xp(yy,xx):
  D[yy][xx][3]=1
  i=1
  while G[yy][xx+i]==".":
    if V[yy][xx]+1>V[yy][xx+i]:
      break
    D[yy][xx+i][2]=1
    D[yy][xx+i][3]=1
    V[yy][xx+i]=min(V[yy][xx+i],V[yy][xx]+1)
    if i==k:
      D[yy][xx+i][3]=0
      Y.append(yy)
      X.append(xx+i)
      break

    Y.append(yy)
    X.append(xx+i)
    i=i+1

while len(X)>0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  if D[y][x][0]==0:
    yn(y,x)
  if D[y][x][1]==0:
    yp(y,x)
  if D[y][x][2]==0:
    xn(y,x)
  if D[y][x][3]==0:
    xp(y,x)

if V[gy][gx]==10**10:
  print(-1)
else:
  print(V[gy][gx])