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
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
X += X[:]
H, W = H+2, W+2
HW = H * W
s, t = x1 * W + y1, x2 * W + y2
ss, tt = s + HW, t + HW
def dijkstra():
    n = 2 * H * W
    h = [s, ss]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    kk = 21
    m = (1 << kk) - 1
    while h:
        x = hpop(h)
        d, i = x >> kk, x & m
        done[i] = 1
        if i < HW:
            for j in (i+1, i-1):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd << kk) + j)
                        D[j] = nd
        else:
            for j in (i+W, i-W):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd << kk) + j)
                        D[j] = nd
            
        j = i + HW if i < HW else i - HW
        nd = (d + K - 1) // K * K
        if X[j]: continue
        if D[j] < 0 or D[j] > nd:
            if done[j] == 0:
                hpush(h, (nd << kk) + j)
                D[j] = nd
    return [-(-a//K) for a in (D[t], D[tt]) if a >= 0]

di = dijkstra()
print(min(di) if di else -1)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
X += X[:]
H, W = H+2, W+2
HW = H * W
s, t = x1 * W + y1, x2 * W + y2
ss, tt = s + HW, t + HW
def dijkstra():
    n = 2 * H * W
    h = [s, ss]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    kk = 21
    m = (1 << kk) - 1
    while h:
        x = hpop(h)
        d, i = x >> kk, x & m
        done[i] = 1
        if i < HW:
            for j in (i+1, i-1):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd << kk) + j)
                        D[j] = nd
        else:
            for j in (i+W, i-W):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd << kk) + j)
                        D[j] = nd
            
        j = i + HW if i < HW else i - HW
        nd = (d + K - 1) // K * K
        if X[j]: continue
        if D[j] < 0 or D[j] > nd:
            if done[j] == 0:
                hpush(h, (nd << kk) + j)
                D[j] = nd
    return [-(-a//K) for a in (D[t], D[tt]) if a >= 0]

di = dijkstra()
print(min(di) if di else -1)

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    h, w, k = map(int, readline().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, readline().split())
    dict = [[-1] * w for _ in range(h)]
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    for i in range(h):
        c = readline().rstrip().decode()
        for j, cc in enumerate(c):
            if cc == '@':
                dict[i][j] = 0
    q = deque()
    q.append((x1, y1))
    dict[x1][y1] = 0
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            exit(print(dict[x][y]))
        for dx, dy in move:
            for i in range(1, k + 1):
                xx = x + dx * i
                yy = y + dy * i
                if 0 > xx or xx >= h or 0 > yy or yy >= w:
                    break
                if 0 <= dict[xx][yy] <= dict[x][y]:
                    break
                if dict[xx][yy] == -1:
                    q.append((xx, yy))
                dict[xx][yy] = dict[x][y] + 1
    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    h, w, k = map(int, readline().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, readline().split())
    c = [readline().rstrip().decode() for _ in range(h)]
    dict = [[-1] * w for _ in range(h)]
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    q.append((x1, y1))
    dict[x1][y1] = 0
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            exit(print(dict[x][y]))
        for dx, dy in move:
            for i in range(1, k + 1):
                xx = x + dx * i
                yy = y + dy * i
                if 0 > xx or xx >= h or 0 > yy or yy >= w:
                    break
                if 0 <= dict[xx][yy] <= dict[x][y] or c[xx][yy] == '@':
                    break
                if dict[xx][yy] == -1:
                    q.append((xx, yy))
                dict[xx][yy] = dict[x][y] + 1
    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    h, w, k = map(int, readline().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, readline().split())
    dict = [[-1] * w for _ in range(h)]
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    for i in range(h):
        c = readline().rstrip().decode()
        for j, cc in enumerate(c):
            if cc == '@':
                dict[i][j] = 0
    q = deque()
    q.append((x1, y1))
    dict[x1][y1] = 0
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            exit(print(dict[x][y]))
        for dx, dy in move:
            for i in range(1, k + 1):
                xx = x + dx * i
                yy = y + dy * i
                if 0 > xx or xx >= h or 0 > yy or yy >= w:
                    break
                if 0 <= dict[xx][yy] <= dict[x][y]:
                    break
                if dict[xx][yy] == -1:
                    q.append((xx, yy))
                dict[xx][yy] = dict[x][y] + 1
    print(-1)


if __name__ == '__main__':
    main()

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

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x : int(x) - 1, input().split())
c = [input().rstrip() for _ in range(H)]
INF = 10**18
dist = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]
dist[x1][y1] = [(1, 0)] * 4
dq = deque()
for i in range(4):
    dq.append((dist[x1][y1][i], x1, y1, i))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while dq:
    d, x, y, i = dq.popleft()

    if d > dist[x][y][i]:
        continue

    for j in range(4):
        nd = (d[0] + 1, 0)
        if dist[x][y][j] > nd:
            dist[x][y][j] = nd
            dq.append((nd, x, y, j))

    nx = x + dx[i]
    ny = y + dy[i]
    if nx < 0 or H <= nx or ny < 0 or W <= ny or c[nx][ny] == '@':
        continue
    if d[1] < K:
        nd = (d[0], d[1] + 1)
        if dist[nx][ny][i] > nd:
            dist[nx][ny][i] = nd
            dq.appendleft((nd, nx, ny, i))
    else:
        nd = (d[0] + 1, 1)
        if dist[nx][ny][i] > nd:
            dist[nx][ny][i] = nd
            dq.append((nd, nx, ny, i))
ans = min(dist[x2][y2])[0]
print(ans if ans < INF else -1)

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

def calc():
  h,w,k=map(int,input().split())
  sy,sx,gy,gx=map(int,input().split())
  sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
  board=[input() for _ in range(h)]
  q=collections.deque()
  q.append((sx,sy))
  checked=[[[0,0,0,0] for _ in range(w)] for _ in range(h)]
  checked[sy][sx][0]=1
  checked[sy][sx][1]=1
  checked[sy][sx][2]=1
  checked[sy][sx][3]=1
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  while len(q)!=0:
    x,y=q.popleft()
    c=cost[y][x]
    for i in range(1,k+1):
      if x+i<w and checked[y][x+i][0]==0 and board[y][x+i]=='.' and c<cost[y][x+i]:
        checked[y][x+i][0]=1
        cost[y][x+i]=c+1
        q.append((x+i,y))
      else:
        break
    for i in range(1,k+1):
      if x-i>=0 and checked[y][x-i][1]==0 and board[y][x-i]=='.' and c<cost[y][x-i]:
        checked[y][x-i][1]=1
        cost[y][x-i]=c+1
        q.append((x-i,y))
      else:
        break
    for i in range(1,k+1):
      if y+i<h and checked[y+i][x][2]==0 and board[y+i][x]=='.' and c<cost[y+i][x]:
        checked[y+i][x][2]=1
        cost[y+i][x]=c+1
        q.append((x,y+i))
      else:
        break
    for i in range(1,k+1):
      if y-i>=0 and checked[y-i][x][3]==0 and board[y-i][x]=='.' and c<cost[y-i][x]:
        checked[y-i][x][3]=1
        cost[y-i][x]=c+1
        q.append((x,y-i))
      else:
        break
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   y=~z,0,z+1,0,~z;i,j=s//w+y[x],s%w+y[x+1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or d[s]>=d[(t:=i*w+j)]:break
   if-~d[s]<d[t]:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or(p:=d[s]+1)>d[(t:=i*w+j)]:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
m+='@'*w,
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
m+='@'*w,
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
          break
        if c[xx][yy] == '.' or (c[xx][yy] != '.' and c[xx][yy] > a):
          c[xx][yy] = a
          qq.append((a+1,xx,yy))
  
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
from collections import deque

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

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

Q = deque([(x1, y1)])
while Q:
    x, y = Q.popleft()
    if (x, y) == (x2, y2):
        print(ans[x][y])
        quit()

    for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for a in range(1, K + 1):
            nx = x + a * di
            ny = y + a * dj

            if not (0 <= nx < H and 0 <= ny < W) or C[nx][ny] == "@" or 0 <= ans[nx][ny] <= ans[x][y]:
                break

            if ans[nx][ny] == -1:
                Q.append((nx, ny))

            ans[nx][ny] = 1 + ans[x][y]

print(-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        for xx,yy in [(1,0),(0,1),(-1,0),(0,-1)]:
            for i in range(1,k+1):
                nx,ny = x+xx*i,y+yy*i
                if cord[ny][nx] == '.':
                    l.append((nx,ny))
                elif type(cord[ny][nx]) != int or cord[ny][nx] < dep+1:
                    break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '

print(bfs(xg,yg))

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        for xx,yy in [(1,0),(0,1),(-1,0),(0,-1)]:
            for i in range(1,k+1):
                nx,ny = x+xx*i,y+yy*i
                if cord[ny][nx] == '.':
                    l.append((nx,ny))
                elif cord[ny][nx] == dep+1:
                    continue
                else:
                    break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '




print(bfs(xg,yg))

Solution (Python):


from collections import deque

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

dist = [[-1] * W for _ in range(H)]
dist[x1][y1] = 0
q = deque()
q.append((x1, y1))

while q:
    (x, y) = q.popleft()
    if (x, y) == (x2, y2):
        break
    for vx, vy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        for k in range(1, K+1):
            nx = x + vx*k
            ny = y + vy*k
            if nx < 0 or nx >= H or ny < 0 or ny >= W or grid[nx][ny] == '@':
                break
            if dist[nx][ny] != -1 and dist[nx][ny] != dist[x][y] + 1:
                break
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

print(dist[x2][y2])

Solution (Python):


from collections import deque

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

dist = [[-1] * W for _ in range(H)]
dist[x1][y1] = 0
q = deque()
q.append((x1, y1))

while q:
    (x, y) = q.popleft()
    if (x, y) == (x2, y2):
        break
    for vx, vy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        for k in range(1, K+1):
            nx = x + vx*k
            ny = y + vy*k
            if nx < 0 or nx >= H or ny < 0 or ny >= W or grid[nx][ny] == '@':
                break
            if dist[nx][ny] != -1 and dist[nx][ny] != dist[x][y] + 1:
                break
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

print(dist[x2][y2])

Solution (Python):
def main():
    h,a,*m=open(0)
    h,w,k,a,b,f,g=map(int,(h+a).split())
    I=h*w
    d=[I]*I
    a=~w+a*w+b
    d[a]=1
    q=[a]
    for s in q:
        for y,x in(1,0),(-1,0),(0,1),(0,-1):
            for z in range(k):
                i,j=s//w+y*~z,s%w+x*~z
                t=i*w+j
                if not h>i>-1<j<w or'.'<m[i][j]or d[t]<=d[s]:break
                if d[t]==I:
                    q+=t,
                    d[t]=d[s]+1
    print(d[~w+f*w+g]%I-1)
main()

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1:
                if cord[y][x+i] == '.':
                    l.append((x+i,y))
                elif cord[y][x+i] == '@' or cord[y][x+i] != dep+1:
                    f1 = False
            if f2:
                if cord[y][x-i] == '.':
                    l.append((x-i,y))
                elif cord[y][x-i] == '@' or cord[y][x-i] != dep+1:
                    f2 = False
            if f3:
                if cord[y+i][x] == '.':
                    l.append((x,y+i))
                elif cord[y+i][x] == '@' or cord[y+i][x] != dep+1:
                    f3 = False
            if f4:
                if cord[y-i][x] == '.':
                    l.append((x,y-i))
                elif cord[y-i][x] == '@' or cord[y-i][x] != dep+1:
                    f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '




print(bfs(xg,yg))

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s+y*~z,t+x*~z;l=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[l]<p:break
   if d[l]==I:q+=(i,j),;d[l]=p
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Solution (Python):
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Solution (Python):
I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Solution (Python):

INF = float("inf")


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

    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    
    
    Q = []
    Q.append((0, x1, y1, 0))
    Q.append((0, x1, y1, 1))
    Q.append((0, x1, y1, 2))
    Q.append((0, x1, y1, 3))
    i = 0
    while i < len(Q):
        curr, x, y, DXY = Q[i]
        dx, dy = DX[DXY], DY[DXY]
        for k in range(1, K+1):
            X, Y = x+k*dx, y+k*dy
            if not (0 <= X < H) or not (0 <= Y < W):
                break
            if 0 < dist[X][Y] < curr+1:
                break
            if dist[X][Y] == curr+1:
                continue
            if c[X][Y] == "@":
                break
            dist[X][Y] = curr+1
            Q.append((curr+1, X, Y, (DXY+1) % 4))
            Q.append((curr+1, X, Y, (DXY-1) % 4))
        else:
            Q.append((curr+1, X, Y, DXY))
        if 0 < dist[x2][y2]:
            print(dist[x2][y2])
            return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

INF = float("inf")


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

    
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__


h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

que = [(sx,sy)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
for x,y in que:
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

Solution (Python):
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

que = [(sx,sy)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
for x,y in que:
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

Solution (Python):
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)

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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


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