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 collections import deque
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

def rights(bd):
    n = len(bd)
    m = len(bd[0])
    rs = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m-1, -1, -1):
            if bd[i][j] == "@":
                rs[i][j] = 0
            elif j == m-1:
                rs[i][j] = 1
            else:
                rs[i][j] = rs[i][j+1] + 1
    return rs

def rotc(bd):
    n = len(bd)
    m = len(bd[0])
    rs = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            rs[j][n-1-i] = bd[i][j]
    return rs


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

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

right = rights(bd)
bd = rotc(bd)
up = rotc(rotc(rotc(rights(bd))))
bd = rotc(bd)
left = rotc(rotc(rights(bd)))
bd = rotc(bd)
down = rotc(rights(bd))
bd = rotc(bd)


q = deque()
rh = 1
while rh < w:
    rh *= 2
ch = 1
while ch < h:
    ch *= 2
ds = [9999999999] * (h*w+h*2*rh+w*2*ch)
q.append(x1*w+y1)
ds[x1*w+y1] = 0







o0 = h*w
o1 = h*w + h*2*rh
while len(q) > 0:
    cur = q.popleft()
    curd = ds[cur]
    if cur < o0:
        r = cur // w
        c = cur % w

        rr = min(c + right[r][c] - 1, c + k) + 1
        ll = max(c - left[r][c] + 1, c - k)
        while ll != 0:
            f = ll & -ll
            if ll + f > rr:
                break
            tar = o0 + r*2*rh + (rh+ll)//f
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            ll += f
        while ll < rr:
            f = rr & -rr
            tar = o0 + r*2*rh + (rh+rr)//f-1
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            rr -= f

        rr = min(r + down[r][c] - 1, r + k) + 1
        ll = max(r - up[r][c] + 1, r - k)
        while ll != 0:
            f = ll & -ll
            if ll + f > rr:
                break
            tar = o1 + c * 2*ch + (ch + ll) // f
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            ll += f
        while ll < rr:
            f = rr & -rr
            tar = o1 + c * 2*ch + (ch + rr) // f - 1
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            rr -= f
    elif cur < o1:
        cur -= o0
        r = cur // (2*rh)
        v = cur % (2*rh)
        if v >= rh:
            tar = r*w + v-rh
            if ds[tar] > curd and bd[r][v-rh] == ".":
                ds[tar] = curd
                q.appendleft(tar)
        else:
            for j in range(2*v, 2*v+2):
                tar = o0 + r*2*rh + j
                if ds[tar] > curd:
                    ds[tar] = curd
                    q.appendleft(tar)
    else:
        cur -= o1
        c = cur // (2 * ch)
        v = cur % (2 * ch)
        if v >= ch:
            tar = (v-ch) * w + c
            if ds[tar] > curd and bd[v-ch][c] == ".":
                ds[tar] = curd
                q.appendleft(tar)
        else:
            for j in range(2 * v, 2 * v + 2):
                tar = o1 + c * 2 * ch + j
                if ds[tar] > curd:
                    ds[tar] = curd
                    q.appendleft(tar)

if ds[x2*w+y2] > 9999999:
    print(-1)
else:
    print(ds[x2*w+y2])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
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)
H, W = H+2, W+2
s, t = x1 * W + y1, x2 * W + y2

def BFS(i0=0):
    dd = [(), (1, -1), (W, -W), (1, -1, W, -W)]
    Q = deque([(i0, 3)])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x, t = Q.popleft()
        if t & 1:
            for d in (1, -1):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append((y, 2))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
        if t & 2:
            for d in (W, -W):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append((y, 1))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
                        
    return D

print(BFS(s)[t])

Solution (Python):
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(i)-1 for i in input().split()]
ans = [[-1] * w for _ in range(h)]
ans[x1][y1] = 0
c = [input() for _ in range(h)]
qu = [(x1, y1)]


for x, y in qu:
    if x == x2 and y == y2:
        print(ans[x2][y2])
        break

    for i in range(x + 1, min(x + k + 1, h)):
        if c[i][y] == "@":
            break
        if ans[i][y] == -1:
            ans[i][y] = ans[x][y] + 1
            qu.append((i, y))
        elif ans[i][y] <= ans[x][y]:
            break
    for i in reversed(range(max(0, x - k), x)):
        if c[i][y] == "@":
            break
        if ans[i][y] == -1:
            ans[i][y] = ans[x][y] + 1
            qu.append((i, y))
        elif ans[i][y] <= ans[x][y]:
            break

    for i in range(y + 1, min(y + k + 1, w)):
        if c[x][i] == "@":
            break
        if ans[x][i] == -1:
            ans[x][i] = ans[x][y] + 1
            qu.append((x, i))
        elif ans[x][i] <= ans[x][y]:
            break
    for i in reversed(range(max(0, y - k), y)):
        if c[x][i] == "@":
            break
        if ans[x][i] == -1:
            ans[x][i] = ans[x][y] + 1
            qu.append((x, i))
        elif ans[x][i] <= ans[x][y]:
            break
else:
    print(-1)

Solution (Python):
from collections import deque

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

G = [['
for _ in range(H):
    tmp = ['
    G.append(tmp)

G.append(['
INF = 10 ** 6+ 10
dp = [[INF] * (W + 2) for _ in range(H + 2)]

que = deque()
que_append = que.append
que_popleft = que.popleft

que_append((x1, y1))
dp[x1][y1] = 0
while que:
    xy = que_popleft()
    x = xy[0]
    y = xy[1]
    tmp = dp[x][y] + 1
    
    if dp[x][y] == dp[x + 1][y] and dp[x][y] != INF:
        pass
    else:
        for k in range(1, K + 1):
            if G[x + k][y] == '.':
                if dp[x + k][y] > tmp:
                    dp[x + k][y] = tmp
                    que_append((x + k, y))
            else:
                break
    if dp[x][y] == dp[x - 1][y] and dp[x][y] != INF:
        pass
    else:
        for k in range(1, K + 1):
            if G[x - k][y] == '.':
                if dp[x - k][y] > tmp:
                    dp[x - k][y] = tmp
                    que_append((x - k, y))
            else:
                break
    if dp[x][y] == dp[x][y + 1] and dp[x][y] != INF:
        pass
    else:
        for k in range(1, K + 1):
            if G[x][y + k] == '.':
                if dp[x][y + k] > tmp:
                    dp[x][y + k] = tmp
                    que_append((x, y + k))
            else:
                break

    if dp[x][y] == dp[x][y - 1] and dp[x][y] != INF:
        pass
    else:
        for k in range(1, K + 1):
            if G[x][y - k] == '.':
                if dp[x][y - k] > tmp:
                    dp[x][y - k] = tmp
                    que_append((x, y - k))
            else:
                break

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

Solution (Python):
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        
        return divisors
    N = I()
    A = LI()
    C = set()
    n = 10**6+1
    D = [False]*n
    ans = 0
    for a in A:
        if a in D:
            D[a] = False
            continue
        D[a] = True
        C.add(a)

    for a in C:
        for i in range(2,1+n//a):
            D[i*a] = False
    ans = sum(D)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue_up = deque()
            queue_d = deque()
            queue_r = deque()
            queue_l = deque()
            queue_up.append(s)
            queue_d.append(s)
            queue_r.append(s)
            queue_l.append(s)
            distance[s[0]][s[1]] = 0
            while (len(queue_up) or len(queue_r) or len(queue_d) or len(queue_l)):
                if queue_up:
                    y, x = queue_up.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y + k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_up.append((ny, nx))
                if queue_d:
                    y, x = queue_d.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y - k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_d.append((ny, nx))
                if queue_r:
                    y, x = queue_r.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x + k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_r.append((ny, nx))
                if queue_l:
                    y, x = queue_l.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x - k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_l.append((ny, nx))

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): 
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      p = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        for k in range(1, K + 1):
          hh = h + i * k
          ww = w + j * k
          if s.L[hh + 1][ww + 1] >= 0:
            if T[hh][ww] == -1 or T[hh][ww] > p + 1:
              q.put([hh, ww])
              T[hh][ww] = p + 1
            elif T[hh][ww] != p + 1:
              break
          else:
            break
            
    return T, k


H, W, K = list(map(int, input().split()))
xy = list(map(int, input().split()))
c = []
for i in range(H):
  c.append(list(input().replace("\n", "")))

for i in range(H):
  for j in range(W):
    if c[i][j] == ".":
      c[i][j] = 0
    else:
      c[i][j] = -1

g = gridMan(c)
g.makeWall()

L, k = g.dist([xy[0] - 1, xy[1] - 1])

print(L[xy[2] - 1][xy[3] - 1])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(100000)

h,w,k = map(int,input().split())
y1,x1,y2,x2 = map(int,input().split())
grid = []
grid.append(['@']*(w+2))
for i in range(h):
    grid.append(['@']+list(input())+['@'])
grid.append(['@']*(w+2))

q = set()
next_q = set()
next_q.add((y1,x1))
ans = 0
while True:
    if not next_q:
        print(-1)
        exit()
    for y,x in next_q:
        grid[y][x] = '@'
    q = next_q
    next_q = set()
    while q:
        y,x = q.pop()
        if (y,x) == (y2,x2):
            print(ans)
            exit()
        for i in range(1,k+1):
            if grid[y+i][x] == '@':
                break
            next_q.add((y+i,x))
        for i in range(1,k+1):
            if grid[y-i][x] == '@':
                break
            next_q.add((y-i,x))
        for i in range(1,k+1):
            if grid[y][x+i] == '@':
                break
            next_q.add((y,x+i))
        for i in range(1,k+1):
            if grid[y][x-i] == '@':
                break
            next_q.add((y,x-i))
    ans += 1