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 sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

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


    from random import randrange
    if randrange(0, 3) == 0:
        
        
        from collections import deque
        seen = [[0] * (w+2) for _ in range(h+2)]
        seen[x1][y1] = 1
        todo = deque([(x1, y1)])
 
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
 
        while len(todo) > 0:
            ix, iy = todo.popleft()
            s = seen[ix][iy] + 1
 
            for j in range(4):
                jx, jy = ix, iy
                dxj, dyj = dx[j], dy[j]
 
                for _ in range(k):
                    jx, jy = jx + dxj, jy + dyj
 
                    if c[jx][jy] == '@':
                        break
 
                    if jx == x2 and jy == y2:
                        print(s - 1)
                        exit()
            
                    if seen[jx][jy] == 0:
                        seen[jx][jy] = s
                        todo.append((jx, jy))



    
    seen = [[-1] * (w+2) for _ in range(h+2)]
    
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)

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

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        
        if seen[xi][yi] == cost:
            xj, yj = xi + dx[direction], yi + dy[direction]
            if c[xj][yj] == '.' and seen[xj][yj] == -1:
                heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue

        if seen[xi][yi] != -1:
            continue
        seen[xi][yi] = cost

        
        if xi == x2 and yi == y2:
            print((cost-1)//k + 1)
            exit()
        
        
        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]

            if c[xj][yj] == '@':
                continue

            if seen[xj][yj] == -1:
                if j == direction:
                    heapq.heappush(todo, (cost+1, xj, yj, j))
                else:
                    heapq.heappush(todo, (((cost-1)//k + 1)*k + 1, xj, yj, j))

    print(-1)

main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(list(input()))
from collections import deque
def bfs(x, y):
    queue = deque([(x, y)])
    d = [[float('inf')]*w for _ in range(h)]
    d[x][y] = 0
    while queue:
        u, v = queue.popleft()
        
        for l in range(1, k + 1):
            p, q = u + l, v
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
        for l in range(1, k + 1):
            p, q = u - l, v
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
        for l in range(1, k + 1):
            p, q = u, v + l
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
        for l in range(1, k + 1):
            p, q = u, v - l
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
    return d
d = bfs(x1 - 1, y1 - 1)
if d[x2 - 1][y2 - 1] == float("inf"):
    print(-1)
else:
    print(d[x2 - 1][y2 - 1])

Solution (Python):
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W + 2)] for _ in range(H + 2)]

dp[0] = [-1] * (W + 2)
dp[H + 1] = [-1] * (W + 2)
for h in range(1, H + 1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W + 1] = -1
    for w in range(1, W + 1):
        if s[w - 1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0



XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K + 1):
                hs, ws = h + dh * sk, w + dw * sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                elif dp[hs][ws] <= dp[h][w]:
                    
                    
                    break
                
                
    


def main():
    bfs(sth, stw, glh, glw)

    if dp[glh][glw] == INF:
        print(-1)
    else:
        print(dp[glh][glw])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1, H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1, W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0



XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                elif dp[hs][ws] <= dp[h][w]:
                    break
                if hs == glh and ws == glw:
                    return dp[h][w] + 1
    return -1


def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1, H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1, W+1):
        if s[w-1] == "@":
            dp[h][w] = -1



XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw, 0))
    dp[sth][stw] = 0

    while len(next_q) != 0:
        
        h, w, c = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws, c+1))
                    dp[hs][ws] = c + 1
                elif dp[hs][ws] <= c:
                    break
                if hs == glh and ws == glw:
                    return c + 1
    return -1


def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10


try:
    profile
except:
    def profile(f): return f

DEBUG = True
if DEBUG:
    def dp(*x):  
        print(*x)
else:
    def dp(*x): pass


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    
    
    
    
    start = x1 * W + y1
    goal = x2 * W + y2

    
    distances = [(INF, 0)] * (H * W * 5)
    
    
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        
        
        dist = distances[pos_dir]
        if dist < (d, frac):
            
            continue
        if pos == goal:
            break

        
        
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

                if distances[to] > newdist:
                    
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        if direction < 2 or direction == 4:  
            
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  
            
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        
        return -1
    else:
        
        
        
        
        
        
        return result[0]



if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    
    data = data.reshape(H, -1)
    
    data = data[:, : W] == b'.'
    
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Solution (Python):


 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = map(int, rl().split())
    sy, sx, gy, gx = map(lambda n: int(n) - 1, rl().split())
    c = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 10
    cost = [[INF] * W for _ in range(H)]
    cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            for k in range(1, K + 1):
                ny, nx = cy + k * dy, cx + k * dx
                if 0 <= ny < H and 0 <= nx < W:
                    if c[ny][nx] == '@':
                        break
                    if cost[ny][nx] <= cost[cy][cx]:
                        break
                    ncost = cost[cy][cx] + 1
                    if ncost < cost[ny][nx]:
                        cost[ny][nx] = ncost
                        que.append((ny, nx))
    print(cost[gy][gx] if cost[gy][gx] != INF else -1)


if __name__ == '__main__':
    solve()

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

h,w,k= map(int, input().split())
sx,sy,gx,gy= map(int, input().split())
maze= [list(input()) for i in range(h)]



def clear_maze(sx, sy, gx, gy):

    INF=10**9
    distance = [[INF for i in range(w)] for j in range(h)]
    
    def bfs():
        
        d=deque()
        d.append((sx, sy))
        distance[sx][sy] =0

        while len(d):
            x, y = d.popleft()

            for i in range(0, 4):
                for j in range(1,k+1):
                    nx, ny = x + [j, 0, -j, 0][i], y + [0, j, 0, -j][i]
                    if not (0 <= nx < h and 0 <= ny < w):
                        break

                    elif maze[nx][ny] == '@' or distance[nx][ny]<=distance[x][y]:
                        break

                    elif distance[nx][ny] == INF:
                        d.append((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()

ans=clear_maze(sx-1,sy-1,gx-1,gy-1)

if  ans==10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1))
while q:
  px,py = q.popleft()
  d = dp[px][py]
  for j in range(1,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= d:
      break
    if dp[px+j][py] == 10**6:
      dp[px+j][py] = d+1
      q.append((px+j,py))
  for j in range(1,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= d:
      break
    if dp[px-j][py] == 10**6:
      dp[px-j][py] = d+1
      q.append((px-j,py))
  for j in range(1,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= d:
      break 
    if dp[px][py+j] == 10**6:
      dp[px][py+j] = d+1
      q.append((px,py+j))
  for j in range(1,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= d:
      break
    if dp[px][py-j] == 10**6:
      dp[px][py-j] = d+1
      q.append((px,py-j))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])

Solution (Python):
import os
import heapq
import sys
import math
import operator
from collections import defaultdict, deque
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m,k=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    ar=[]
    ans=[]
    visited=[]
    for i in range(n):
        visited.append([False]*m)
        ar.append(input())
        ans.append([0]*m)

    if(ar[x1-1][y1-1]=='@' or ar[x2-1][y2-1]=='@'):
        print(-1)
    q=deque()
    q.append((x1-1,y1-1))
    br=[(-1,0),(1,0),(0,1),(0,-1)]
    
    while(q):
        a,b=q.popleft()
        
        if(a==x2-1 and b==y2-1):
            print(ans[a][b])
            exit()
        for p,r in br:
            for i in range(1,k+1):
                x=a+i*p
                y=b+i*r
                if not (0<=x<n and 0<=y<m) or ar[x][y]=='@' or (x==x1-1 and y==y1-1):
                    break
                if(0<ans[x][y]<=ans[a][b]):
                    break
                
                ans[x][y]=ans[a][b]+1
                
                if(not visited[x][y]):
                    q.append([x,y])
                    visited[x][y]=True
    print(-1)







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def resolve():
    H,W,K = map(int,input().split())
    ys, xs, yg, xg = map(int,input().split())

    board = [['@']*(W+2)]
    for i in range(H):
        board.append(['@'] + list(input())+['@'])
    board.append(['@']*(W+2))
    board[ys][xs] = '

    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 board[y][x+i] == '.':
                    l.append((x+i,y))
                elif board[y][x+i] == '@' or board[y][x+i] != dep+1:
                    f1 = False 
            if f2:
                if board[y][x-i] == '.':
                    l.append((x-i,y))
                elif board[y][x-i] == '@' or board[y][x-i] != dep+1:
                    f2 = False 
            if f3:
                if board[y+i][x] == '.':
                    l.append((x,y+i))
                elif board[y+i][x] == '@' or board[y+i][x] != dep+1:
                    f3 = False 
            if f4:
                if board[y-i][x] == '.':
                    l.append((x,y-i))
                elif board[y-i][x] == '@' or board[y-i][x] != dep+1:
                    f4 = False 
            if not(f1 or f2 or f3 or f4):
                break
        for nx,ny in l:
            if board[ny][nx] == '.':
                board[ny][nx] = dep + 1
                if (nx,ny) == (xg,yg):
                    print(dep+1)
                    return 
                else:
                    queue.append((nx,ny,dep+1))
    print(-1)
    return 
resolve()

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



H,W,K = LI()
x1,y1,x2,y2 = LI()
c = [list(map(str,input())) for _ in range(H)]

def grid_bfs(S,s,default=-1):
    dist = [[default]*W for _ in range(H)]
    can_visit_mark = ['.']
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    dist[s[0]][s[1]] = 0
    q = [s]
    counter = 1
    while q:
        q1 = []
        for now in q:
            for delta in d:
                for i in range(1,K+1):
                    new = (now[0]+i*delta[0], now[1]+i*delta[1])
                    if 0 <= new[0] <= H-1 and 0 <= new[1] <= W-1:
                        if S[new[0]][new[1]] in can_visit_mark:  
                            if dist[new[0]][new[1]] == default:
                                dist[new[0]][new[1]] = counter
                                q1.append(new)
                            elif dist[now[0]][now[1]] < dist[new[0]][new[1]]:
                                continue
                            else:
                                break
                        else:
                            break
                    else:
                        break
        if dist[x2-1][y2-1] != default:
            return dist[x2-1][y2-1]
        q = q1
        counter += 1
    return -1

print(grid_bfs(c,(x1-1,y1-1)))

Solution (Python):
from collections import deque
h, w, k = map(int, input().split())
n = h*w
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])


def bfs(init_v):
    next_v = deque([init_v])
    dist = [-1]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = divmod(v, w)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            for a in range(1, k+1):
                x, y = i+di*a, j+dj*a
                if x < 0 or h <= x or y < 0 or w <= y:
                    break
                v2 = x*w+y
                if fld[v2] == '@':
                    break
                if dist[v2] != -1 and dist[v2] <= dist[v]:
                    break
                if dist[v2] != -1:
                    continue
                dist[v2] = dist[v]+1
                next_v.append(v2)
    return dist


dist = bfs(x1*w+y1)
print(dist[x2*w+y2])

Solution (Python):
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()
INF = 10**18
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

def main():
    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
    C = [input() for _ in range(H)]

    """
    まずはKの制約がない時を考える。単純なBFSでは明らかに間に合わないが、
    「位置」と「向き」の直積を頂点として扱うのがポイント。
    隣の頂点に同じ向きで移動するのにコスト0、同じ頂点で向きを変えるのにコスト1かかるとして
    辺を張れば、ダイクストラにより計算量O((4HW + 4HW) * log(4HW))で解ける。

    ではKの制約がある時はどうするかというと、コストを(従来のコスト, 直線移動距離)のペアに変更する。
    直線移動距離がKを超えたら従来のコストを１つ繰り上げる。
    このペアによるコストは辞書式順序により全順序構造を持つので同様にダイクストラで扱える。

    さらに実はこのコストはペアで扱わないにすることもでき、
        直線移動のコスト＝1/K
        方向転換のコスト＝切り上げ
    と定めると整数部分が本問で求めるコストになっている。
    少数は少し怖いので実際にはK倍して扱う。
    """

    
    def toId(i, j, v):
        return (i * W + j) * 4 + v

    dist = [INF] * (H * W * 4)
    q = []

    
    def push(i, j, v, x):
        id = toId(i, j, v)
        if dist[id] <= x: return
        dist[id] = x
        heappush(q, (x, id))

    
    for v in range(4): push(x1, y1, v, 0)
    while q:
        x, id = heappop(q)
        if dist[id] != x: continue 
        i, j, v = (id // 4) // W, (id // 4) % W, id % 4
        
        push(i, j, (v + 1) % 4, (x + K - 1) // K * K)
        push(i, j, (v + 2) % 4, (x + K - 1) // K * K)
        push(i, j, (v + 3) % 4, (x + K - 1) // K * K)
        
        ni, nj = i + di[v], j + dj[v]
        if 0 <= ni < H and 0 <= nj < W and C[ni][nj] == '.':
            push(ni, nj, v, x + 1)
    ans = min(dist[toId(x2, y2, v)] for v in range(4))
    if ans == INF: print(-1)
    else: print((ans + K - 1) // K)
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
si, sj, ti, tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
b = [input() for _ in range(h)]
ans = [[-1]* w for _ in range(h)]
ans[si][sj] = 0
from collections import deque
d = deque()
d.append((si, sj))
while d:
  x, y = d.popleft()
  if x == ti and y == tj:
    print(ans[x][y])
    exit()
  for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
    for i in range(1, k+1):
      xx = x+dx*i
      yy = y+dy*i
      if not(0<= xx < h and 0<= yy < w) or b[xx][yy] == '@':
        break
      if 0 <= ans[xx][yy] <= ans[x][y]:
        break
      if ans[xx][yy] == -1:
        d.append((xx, yy))
      ans[xx][yy] = ans[x][y] + 1
print(-1)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
                if dist + 1 > dp[ny][nx]:
                    break
            else:
                break
print(-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 = [(0, s), (0, ss)]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    while h:
        d, i = hpop(h)
        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, 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, 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, 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)