AtCoder Beginner Contest 170 - Pond Skater

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-----
3 5 2
3 2 3 4
.....
.@..@
..@..

-----Sample Output-----
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).

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
INF = float('inf')
from collections import deque

def mbfs(G, sh, sw, H, W):
	dist = [[INF] * W for i in range(H)]
	dist[sh][sw] = 0
	d = deque()
	d.append([sh, sw])
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	while len(d) != 0:
		h = d[0][0]
		w = d[0][1]
		d.popleft()
		for dir in range(4):
			for k in range(1, K + 1):
				nh = h + dx[dir] * k
				nw = w + dy[dir] * k
				if nh > H - 1 or nh < 0 or nw > W - 1 or (nw < 0):
					break
				if G[nh][nw] == '@':
					break
				if dist[nh][nw] <= dist[h][w]:
					break
				if dist[nh][nw] == dist[h][w] + 1:
					continue
				else:
					dist[nh][nw] = dist[h][w] + 1
					d.append([nh, nw])
	return dist
(H, W, K) = map(int, input().split())
(sx, sy, gx, gy) = map(lambda x: int(x) - 1, input().split())
c = [list(input()) for i in range(H)]
dist = mbfs(c, sx, sy, H, W)
ans = dist[gx][gy]
print(ans if ans != INF else -1)


import collections
import sys
INF = 10 ** 10

def main(H, W, K, x1, y1, x2, y2, C):
	dist = [[INF] * W for _ in range(H)]
	q = collections.deque([(x1, y1)])
	dist[x1][y1] = 0
	while q:
		(i, j) = q.popleft()
		d = dist[i][j]
		for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			for dt in range(1, K + 1):
				(ni, nj) = (i + di * dt, j + dj * dt)
				if not (0 <= ni < H and 0 <= nj < W):
					break
				if C[ni][nj] == '@':
					break
				if dist[ni][nj] == d + 1:
					continue
				if dist[ni][nj] < d + 1:
					break
				dist[ni][nj] = d + 1
				q.append((ni, nj))
	ans = dist[x2][y2]
	if ans == INF:
		print(-1)
	else:
		print(ans)
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)]
main(H, W, K, x1, y1, x2, y2, C)


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)


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
from collections import deque
inf = 10 ** 18
(H, W, K) = mapint()
(y1, x1, y2, x2) = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]
checked = [[-1] * W for _ in range(H)]
checked[y1 - 1][x1 - 1] = 0
queue = deque([(y1 - 1, x1 - 1)])

def bfs(queue):
	while len(queue):
		(y, x) = queue.popleft()
		if y == y2 - 1 and x == x2 - 1:
			return checked[y][x]
		for (dy, dx) in dirc:
			for i in range(1, K + 1):
				(ny, nx) = (y + dy * i, x + dx * i)
				if ny >= H or ny < 0 or nx >= W or (nx < 0):
					break
				if query[ny][nx] == '@':
					break
				if checked[ny][nx] < 0:
					checked[ny][nx] = checked[y][x] + 1
					queue.append((ny, nx))
				elif checked[ny][nx] <= checked[y][x]:
					break
	return -1
print(bfs(queue))


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)


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))
	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 board[y][x + i] == '.' and (c < cost[y][x + i]):
				if cost[y][x + i] > c + 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 board[y][x - i] == '.' and (c < cost[y][x - i]):
				if cost[y][x - i] > c + 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 board[y + i][x] == '.' and (c < cost[y + i][x]):
				if cost[y + i][x] > c + 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 board[y - i][x] == '.' and (c < cost[y - i][x]):
				if cost[y - i][x] > c + 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()


import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
(H, W, K) = map(int, input().split())
(sy, sx, gy, gx) = map(int, input().split())
st = sx + sy * (W + 2)
gl = gx + gy * (W + 2)
c = ['@'] * (W + 2)
for i in range(H):
	c.extend(['@'] + list(input()) + ['@'])
c.extend(['@'] * (W + 2))
que = deque()
dist = [INF] * (W + 2) * (H + 2)
que.append(st)
dist[st] = 0
d = (-1, 1, W + 2, -(W + 2))
while que:
	v = que.popleft()
	for k in range(4):
		nv = v
		for _ in range(K):
			nv += +d[k]
			if c[nv] == '.' and dist[nv] > dist[v]:
				if dist[nv] == INF:
					dist[nv] = dist[v] + 1
					que.append(nv)
			else:
				break
print(dist[gl] if dist[gl] != INF else -1)


(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1 - 1][y1 - 1] = 0
que = {(x1 - 1, y1 - 1): 0}
step = 1
while len(que) > 0:
	que_next = {}
	for q in que.keys():
		(x, y) = (q[0], q[1])
		for i in range(1, K + 1):
			if x - i < 0:
				break
			if C[x - i][y] == '@' or T[x - i][y] == 1:
				break
			if x - i == x2 - 1 and y == y2 - 1:
				print(step)
				exit()
			que_next[x - i, y] = 0
		for i in range(1, K + 1):
			if x + i > H - 1:
				break
			if C[x + i][y] == '@' or T[x + i][y] == 1:
				break
			if x + i == x2 - 1 and y == y2 - 1:
				print(step)
				exit()
			que_next[x + i, y] = 0
		for i in range(1, K + 1):
			if y - i < 0:
				break
			if C[x][y - i] == '@' or T[x][y - i] == 1:
				break
			if x == x2 - 1 and y - i == y2 - 1:
				print(step)
				exit()
			que_next[x, y - i] = 0
		for i in range(1, K + 1):
			if y + i > W - 1:
				break
			if C[x][y + i] == '@' or T[x][y + i] == 1:
				break
			if x == x2 - 1 and y + i == y2 - 1:
				print(step)
				exit()
			que_next[x, y + i] = 0
	que = que_next
	for q in que.keys():
		T[q[0]][q[1]] = 1
	step += 1
print(-1)


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


import sys
from collections import deque

def input():
	return sys.stdin.readline().rstrip()

def main():

	def bfs():
		inf = 10000000.0
		dist = [[inf] * w for _ in range(h)]
		dist[xs][ys] = 0
		que = deque([(xs, ys)])
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		while que:
			(x, y) = que.popleft()
			for i in range(4):
				(nx, ny) = (x, y)
				for _ in range(k):
					nx += dx[i]
					ny += dy[i]
					if nx < 0 or nx >= h or ny < 0 or (ny >= w):
						break
					if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]:
						break
					if dist[nx][ny] > dist[x][y] + 1:
						dist[nx][ny] = dist[x][y] + 1
						que.append((nx, ny))
		if dist[xg][yg] == inf:
			print(-1)
		else:
			print(dist[xg][yg])
	(h, w, k) = map(int, input().split())
	(xs, ys, xg, yg) = map(lambda x: int(x) - 1, input().split())
	field = [input() for _ in range(h)]
	bfs()

def __starting_point():
	main()
__starting_point()


import sys
inf = 1000002
sys.setrecursionlimit(inf)
from collections import deque
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
c = [input() for i in range(h)]
dp = [[inf if c[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
now = deque([[x1 - 1, y1 - 1]])
dp[x1 - 1][y1 - 1] = 0

def bfs(d):
	global dp, now
	l = len(now)
	dp_sub = deque()
	cand = set()
	for i in range(l):
		(x, y) = now.popleft()
		for j in range(1, min(k + 1, w - y)):
			if dp[x][y + j] == inf:
				dp_sub += [[x, y + j, d]]
				cand.add((x, y + j))
			else:
				break
		for j in range(1, min(k + 1, y + 1)):
			if dp[x][y - j] == inf:
				dp_sub += [[x, y - j, d]]
				cand.add((x, y - j))
			else:
				break
		for j in range(1, min(k + 1, h - x)):
			if dp[x + j][y] == inf:
				dp_sub += [[x + j, y, d]]
				cand.add((x + j, y))
			else:
				break
		for j in range(1, min(k + 1, x + 1)):
			if dp[x - j][y] == inf:
				dp_sub += [[x - j, y, d]]
				cand.add((x - j, y))
			else:
				break
	while dp_sub != deque([]):
		e = dp_sub.popleft()
		dp[e[0]][e[1]] = e[2]
	for i in cand:
		now += [i]
	if l != 0:
		bfs(d + 1)
bfs(1)
print(dp[x2 - 1][y2 - 1] if dp[x2 - 1][y2 - 1] != inf else -1)


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

def main():
	(h, w, k) = list(map(int, input().split()))
	(sx, sy, gx, gy) = list(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)

def __starting_point():
	main()
__starting_point()


import math
import queue
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	(h, w, k) = map(int, ipt().split())
	(x1, y1, x2, y2) = map(int, ipt().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	ms = [input() + '@' for _ in range(h)]
	ms.append('@' * (w + 1))
	hq = []
	al = [[10 ** 18] * w for _ in range(h)]
	al[x1][y1] = 0
	dr = [(0, 1), (1, 0), (0, -1), (-1, 0)]
	hpq.heappush(hq, (0, x1, y1))
	while hq:
		(c, x, y) = hpq.heappop(hq)
		cn = c + 1
		if x == x2 and y == y2:
			print(c)
			exit()
		for (dx, dy) in dr:
			xx = x
			yy = y
			for i in range(k):
				xx += dx
				yy += dy
				if ms[xx][yy] == '.':
					if al[xx][yy] > cn:
						al[xx][yy] = cn
						hpq.heappush(hq, (cn, xx, yy))
					elif al[xx][yy] == cn:
						continue
					else:
						break
				else:
					break
	print(-1)
	return
main()


import sys
import math
from collections import defaultdict, deque

def r():
	return int(input())

def rm():
	return map(int, input().split())

def rl():
	return list(map(int, input().split()))

def bfs(maze, visited, sy, sx, gy, gx):
	queue = deque([[sy, sx]])
	visited[sy][sx] = 0
	while queue:
		(y, x) = queue.popleft()
		if [y, x] == [gy, gx]:
			return visited[y][x]
		for (j, k) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			p = 0
			l = 1
			while p == 0:
				(new_y, new_x) = (y + j * l, x + k * l)
				if 0 <= new_y < H and 0 <= new_x < W:
					if maze[new_y][new_x] == '@':
						p = 1
					elif visited[new_y][new_x] == -1:
						visited[new_y][new_x] = visited[y][x] + 1
						queue.append([new_y, new_x])
					elif visited[new_y][new_x] < visited[y][x] + 1:
						p = 1
				else:
					p = 1
				l += 1
				if l == K + 1:
					p = 1
(H, W, K) = rm()
(x1, y1, x2, y2) = rm()
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
C = [0] * H
for i in range(H):
	C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
print(visited[x2][y2])


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


from heapq import heappop, heappush

def solve(field, s, t, k):
	INF = 10 ** 18
	ans = [[INF, INF] for _ in field]
	ans[s][0] = ans[s][1] = 0
	MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]
	q = [(0, s, 0)]
	while q:
		(cost, v, direction) = heappop(q)
		if v == t:
			return (cost - 1) // k + 1
		ceiling = -1
		for (di, ax) in MOVE:
			u = v + di
			if field[u] == '@':
				continue
			nc = cost + 1 if di == direction else ceiling
			if nc == -1:
				nc = ceiling = ((cost - 1) // k + 1) * k + 1
			if ans[u][ax] <= nc:
				continue
			ans[u][ax] = nc
			heappush(q, (nc, u, di))
	return -1
(h, w, k) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
h2 = h + 2
w2 = w + 2
field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
	field.append('@')
	field.append(row)
	field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))


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)


from collections import deque
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
maze = []
maze.append(['@'] * (W + 2))
for _ in range(H):
	row = list(input())
	maze.append(['@'] + row + ['@'])
maze.append(['@'] * (W + 2))
q = deque([(x1, y1)])
depth = 0
while q:
	for (i, j) in q:
		maze[i][j] = '@'
	new_q = set()
	l = len(q)
	for _ in range(l):
		(x, y) = q.pop()
		if (x, y) == (x2, y2):
			print(depth)
			exit()
		for i in range(1, K + 1):
			if maze[x - i][y] == '@':
				break
			new_q.add((x - i, y))
		for i in range(1, K + 1):
			if maze[x + i][y] == '@':
				break
			new_q.add((x + i, y))
		for i in range(1, K + 1):
			if maze[x][y - i] == '@':
				break
			new_q.add((x, y - i))
		for i in range(1, K + 1):
			if maze[x][y + i] == '@':
				break
			new_q.add((x, y + i))
	q = deque(list(new_q))
	depth += 1
print(-1)


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)


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

def __starting_point():
	main()
__starting_point()


from collections import deque
import sys
N_MAX = 200000 + 5
(H, W, K) = list(map(int, input().split()))
(sth, stw, glh, glw) = list(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)

def __starting_point():
	main()
__starting_point()


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


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)


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


from queue import Queue
INF = 10 ** 6 + 1
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
MAP = []
for _ in range(H):
	MAP.append(list(input()))
D = [[INF for i in range(W)] for j in range(H)]
D[x1 - 1][y1 - 1] = 0
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
q = Queue()
q.put([x1 - 1, y1 - 1, 0])
while not q.empty():
	(x, y, k) = q.get()
	if x == x2 - 1 and y == y2 - 1:
		break
	for i in range(4):
		nx = x
		ny = y
		for _ in range(K):
			nx += tx[i]
			ny += ty[i]
			if not (0 <= nx <= H - 1 and 0 <= ny <= W - 1) or MAP[nx][ny] == '@' or D[nx][ny] < k + 1:
				break
			if D[nx][ny] == k + 1:
				continue
			D[nx][ny] = k + 1
			q.put([nx, ny, k + 1])
if D[x2 - 1][y2 - 1] == INF:
	print(-1)
else:
	print(D[x2 - 1][y2 - 1])


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


import sys
from heapq import heappush, heappop, heapify

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return [LIST() for _ in range(n)]

def main():
	(H, W, K) = MAP()
	HH = max(H, W) + 2
	(x1, y1, x2, y2) = LIST()
	c = [[-1] + [0 if c == '.' else -1 for c in input()] + [-1] for i in range(H)]
	c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
	stack = []
	heappush(stack, (0, x1, y1, 0))
	heappush(stack, (0, x1, y1, 1))
	heappush(stack, (0, x1, y1, 2))
	heappush(stack, (0, x1, y1, 3))
	DX = (1, 0, -1, 0)
	DY = (0, 1, 0, -1)
	while stack:
		new_stack = []
		while stack:
			(curr, x, y, d) = heappop(stack)
			flag = True
			a = curr + 1
			for k in range(1, K + 1):
				(xx, yy) = (x + k * DX[d], y + k * DY[d])
				if c[xx][yy] == 0:
					b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
					if b == 0 or b == a + 1:
						heappush(new_stack, (a, xx, yy, (d - 1) % 4))
					b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
					if b == 0 or b == a + 1:
						heappush(new_stack, (a, xx, yy, (d + 1) % 4))
					c[xx][yy] = a
				elif c[xx][yy] != a:
					flag = False
					break
			if flag:
				heappush(new_stack, (a, xx, yy, d))
			if c[x2][y2] > 0:
				print(c[x2][y2])
				return
		stack = new_stack
	print(-1)
	return

def __starting_point():
	main()
__starting_point()


from collections import deque
import sys

def bfs(x1, y1, d):
	q = deque()
	q.append((d, x1, y1))
	while q:
		(d, x1, y1) = q.popleft()
		M[x1][y1] = d
		if [x1, y1] == [xg, yg]:
			return
		for (dx, dy) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
			for k in range(1, K + 1):
				x2 = x1 + dx * k
				y2 = y1 + dy * k
				if 0 <= x2 < H and 0 <= y2 < W:
					if m[x2][y2] == '@':
						break
					elif M[x2][y2] == -1:
						M[x2][y2] = d + 1
						q.append((d + 1, x2, y2))
					elif M[x2][y2] < d + 1:
						break
				else:
					break
(H, W, K) = list(map(int, input().split()))
(xs, ys, xg, yg) = list(map(int, input().split()))
(xs, ys, xg, yg) = (xs - 1, ys - 1, xg - 1, yg - 1)
m = []
for i in range(H):
	m.append(list(map(str, sys.stdin.readline().strip())))
M = [[-1] * W for i in range(H)]
bfs(xs, ys, 0)
print(M[xg][yg])


from collections import deque
(h, w, k) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
dp = [[-1] * w for _ in range(h)]
que = deque()
c = [input() for _ in range(h)]
dp[x1][y1] = 0
que.append((x1, y1))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while que:
	(x, y) = que.popleft()
	if x == x2 and y == y2:
		exit(print(dp[x][y]))
	for (dx, dy) in [[1, 0], [-1, 0], [0, -1], [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 c[xx][yy] == '@':
				break
			if 0 <= dp[xx][yy] <= dp[x][y]:
				break
			if dp[xx][yy] == -1:
				que.append((xx, yy))
			dp[xx][yy] = dp[x][y] + 1
print(-1)


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


import sys
input = sys.stdin.readline
from collections import deque
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
MAP = [list(input().strip()) for i in range(H)]
for i in range(H):
	for j in range(W):
		if MAP[i][j] == '.':
			MAP[i][j] = 1 << 30
		else:
			MAP[i][j] = -1
Q = deque()
Q.append((x1 - 1, y1 - 1))
MAP[x1 - 1][y1 - 1] = 0
while Q:
	(x, y) = Q.pop()
	for i in range(1, K + 1):
		if 0 <= x + i < H and 0 <= y < W and (MAP[x + i][y] == 1 << 30 or MAP[x + i][y] > MAP[x][y]):
			if MAP[x + i][y] == 1 << 30:
				MAP[x + i][y] = MAP[x][y] + 1
				Q.appendleft((x + i, y))
		else:
			break
	for i in range(1, K + 1):
		if 0 <= x - i < H and 0 <= y < W and (MAP[x - i][y] == 1 << 30 or MAP[x - i][y] > MAP[x][y]):
			if MAP[x - i][y] == 1 << 30:
				MAP[x - i][y] = MAP[x][y] + 1
				Q.appendleft((x - i, y))
		else:
			break
	for i in range(1, K + 1):
		if 0 <= x < H and 0 <= y + i < W and (MAP[x][y + i] == 1 << 30 or MAP[x][y + i] > MAP[x][y]):
			if MAP[x][y + i] == 1 << 30:
				MAP[x][y + i] = MAP[x][y] + 1
				Q.appendleft((x, y + i))
		else:
			break
	for i in range(1, K + 1):
		if 0 <= x < H and 0 <= y - i < W and (MAP[x][y - i] == 1 << 30 or MAP[x][y - i] > MAP[x][y]):
			if MAP[x][y - i] == 1 << 30:
				MAP[x][y - i] = MAP[x][y] + 1
				Q.appendleft((x, y - i))
		else:
			break
if MAP[x2 - 1][y2 - 1] == 1 << 30:
	print(-1)
else:
	print(MAP[x2 - 1][y2 - 1])


from collections import deque
(he, w, k) = map(int, input().split())
(sx, sy, gx, gy) = map(int, input().split())
l = [list(input()) for i in range(he)]
sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float('INF')] * w for i in range(he)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
d[sx][sy] = 0
q.append((0, sx, sy))
while q:
	(dis, bx, by) = q.popleft()
	if bx == gx and by == gy:
		continue
	for i in range(4):
		for j in range(1, k + 1):
			nx = bx + dx[i] * j
			ny = by + dy[i] * j
			if 0 > nx or 0 > ny or nx >= he or (ny >= w):
				break
			if l[nx][ny] == '@':
				break
			if d[nx][ny] <= dis:
				break
			if d[nx][ny] > dis + 1:
				d[nx][ny] = dis + 1
				q.append((dis + 1, nx, ny))
if d[gx][gy] == float('INF'):
	print(-1)
else:
	print(d[gx][gy])


(H, W, K) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
C = []
nx = set([])
for _ in range(H):
	C.append(list(input()))

def keiro(x, y, k):
	i = 1
	while True:
		if y + i > W - 1 or C[x][y + i] != '.' or i > k:
			break
		else:
			if (x, y + i) not in nx:
				nx.add((x, y + i))
			i += 1
	i = 1
	while True:
		if y - i < 0 or C[x][y - i] != '.' or i > k:
			break
		else:
			if (x, y - i) not in nx:
				nx.add((x, y - i))
			i += 1
	i = 1
	while True:
		if x + i > H - 1 or C[x + i][y] != '.' or i > k:
			break
		else:
			if (x + i, y) not in nx:
				nx.add((x + i, y))
			i += 1
	i = 1
	while True:
		if x - i < 0 or C[x - i][y] != '.' or i > k:
			break
		else:
			if (x - i, y) not in nx:
				nx.add((x - i, y))
			i += 1
	return 0
C[x1 - 1][y1 - 1] = 0
keiro(x1 - 1, y1 - 1, K)
taisho = nx.copy()
result = 1
for j in nx:
	C[j[0]][j[1]] = result
while C[x2 - 1][y2 - 1] == '.':
	nx = set([])
	if len(taisho) == 0 or result > 10 ** 6:
		result = -1
		break
	for l in taisho:
		keiro(l[0], l[1], K)
	result += 1
	for j in nx:
		C[j[0]][j[1]] = result
	taisho = nx.copy()
print(result)


import sys
from collections import deque

def bfs(x1, y1, d):
	q = deque([])
	q.append((d, x1, y1))
	M[x1][y1] = d
	while q:
		(d, x1, y1) = q.popleft()
		if [x1, y1] == [xg, yg]:
			print(d)
			return
		for (dx, dy) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
			for k in range(1, K + 1):
				x2 = x1 + dx * k
				y2 = y1 + dy * k
				if x2 < 0 or x2 >= H:
					break
				if y2 < 0 or y2 >= W:
					break
				if m[x2][y2] == '@':
					break
				if M[x2][y2] < d + 1:
					break
				if M[x2][y2] == d + 1:
					continue
				q.append((d + 1, x2, y2))
				M[x2][y2] = d + 1
	print(-1)
(H, W, K) = list(map(int, sys.stdin.readline().strip().split()))
(xs, ys, xg, yg) = list(map(int, sys.stdin.readline().strip().split()))
xg -= 1
yg -= 1
m = []
for _ in range(H):
	m.append(list(map(str, sys.stdin.readline().strip())))
M = [[float('inf')] * W for _ in range(H)]
bfs(xs - 1, ys - 1, 0)


import sys
sys.setrecursionlimit(10 ** 8)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return [LIST() for _ in range(n)]
INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 1e-06
KETA = 10 ** 7

def main():
	(H, W, K) = MAP()
	(x1, y1, x2, y2) = LIST()
	c = [[-1] + [0 if c == '.' else -1 for c in input()] + [-1] for i in range(H)]
	c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
	c[x1][y1] = 0
	stack = [(x1 * KETA + y1 << 2) + 0, (x1 * KETA + y1 << 2) + 1, (x1 * KETA + y1 << 2) + 2, (x1 * KETA + y1 << 2) + 3]
	DX = (1, 0, -1, 0)
	DY = (0, 1, 0, -1)
	head = 0
	while head < len(stack):
		b = stack[head]
		head += 1
		d = b % 4
		(x, y) = divmod(b >> 2, KETA)
		flag = True
		a = c[x][y] + 1
		for k in range(1, K + 1):
			(xx, yy) = (x + k * DX[d], y + k * DY[d])
			if c[xx][yy] == 0:
				stack.append((xx * KETA + yy << 2) + (d - 1) % 4)
				stack.append((xx * KETA + yy << 2) + (d + 1) % 4)
				c[xx][yy] = a
			elif c[xx][yy] != a:
				flag = False
				break
		if flag:
			stack.append((xx * KETA + yy << 2) + d)
		if c[x2][y2] > 0:
			print(c[x2][y2])
			return
	print(-1)
	return
main()


from collections import deque
moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
INF = float('inf')
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]
cost = [[INF] * w for _ in range(h)]
todo = deque()
todo.append((x1, y1))
cost[x1][y1] = 0
while todo:
	(x, y) = todo.popleft()
	for (vx, vy) in moves:
		for kk in range(1, k + 1):
			nx = x + vx * kk
			ny = y + vy * kk
			if not 0 <= nx < h or not 0 <= ny < w:
				break
			if maze[nx][ny] == '@':
				break
			if cost[nx][ny] <= cost[x][y]:
				break
			if cost[nx][ny] == INF:
				cost[nx][ny] = cost[x][y] + 1
				todo.append((nx, ny))
ans = cost[x2][y2]
if ans == INF:
	ans = -1
print(ans)


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

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


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math

def LI():
	return [int(x) for x in sys.stdin.readline().split()]
dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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


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()
(h, w, K) = na()
(x1, y1, x2, y2) = na()
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
bd = [ns() for _ in range(h)]
q = deque()
ds = [9999999999999999] * (h * w)
q.append((x1, y1))
ds[x1 * w + y1] = 0
dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)
while len(q) > 0:
	(r, c) = q.popleft()
	for i in range(4):
		for j in range(1, K + 1):
			(nr, nc) = (r + dr[i] * j, c + dc[i] * j)
			if 0 <= nr < h and 0 <= nc < w and (bd[nr][nc] != '@'):
				nd = ds[r * w + c] + 1
				if nd < ds[nr * w + nc]:
					ds[nr * w + nc] = nd
					q.append((nr, nc))
				elif nd <= ds[nr * w + nc]:
					continue
				else:
					break
			else:
				break
ans = ds[x2 * w + y2]
if ans < 999999999999:
	print(ans)
else:
	print(-1)


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

def bfs(i1, j1) -> list:
	(U, D, L, R) = (0, 1, 2, 3)
	INF = 10 ** 18
	dist = [[INF] * w for _ in range(h)]
	dist[i1][j1] = 0
	q = deque([(0, i1, j1)])
	while q:
		(d, i, j) = q.popleft()
		for (di, dj) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
			for length in range(1, k + 1):
				nxt_i = i + di * length
				nxt_j = j + dj * length
				if not (0 <= nxt_i < h and 0 <= nxt_j < w):
					break
				if c[nxt_i][nxt_j] == '@':
					break
				if dist[i][j] + 1 > dist[nxt_i][nxt_j]:
					break
				if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
					dist[nxt_i][nxt_j] = dist[i][j] + 1
					q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
	return dist
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
c = [input() for i in range(h)]
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())
pond = [list(input()) for _ in range(H)]
inf = float('inf')
cost = [[inf] * W for _ in range(H)]
cost[x1][y1] = 0
from heapq import heappop, heappush
hq = [(0, x1, y1)]
while hq:
	(t, x, y) = heappop(hq)
	if x == x2 and y == y2:
		print(t)
		exit()
	for i in range(1, K + 1):
		if x - i < 0 or pond[x - i][y] == '@' or cost[x - i][y] < t + 1:
			break
		if cost[x - i][y] > t + 1:
			cost[x - i][y] = t + 1
			heappush(hq, (t + 1, x - i, y))
	for i in range(1, K + 1):
		if y + i > W - 1 or pond[x][y + i] == '@' or cost[x][y + i] < t + 1:
			break
		if cost[x][y + i] > t + 1:
			cost[x][y + i] = t + 1
			heappush(hq, (t + 1, x, y + i))
	for i in range(1, K + 1):
		if x + i > H - 1 or pond[x + i][y] == '@' or cost[x + i][y] < t + 1:
			break
		if cost[x + i][y] > t + 1:
			cost[x + i][y] = t + 1
			heappush(hq, (t + 1, x + i, y))
	for i in range(1, K + 1):
		if y - i < 0 or pond[x][y - i] == '@' or cost[x][y - i] < t + 1:
			break
		if cost[x][y - i] > t + 1:
			cost[x][y - i] = t + 1
			heappush(hq, (t + 1, x, y - i))
print(-1)


from collections import deque
(h, w, k) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
dp = [[-1] * w for _ in range(h)]
que = deque()
c = [input() for _ in range(h)]
dp[x1][y1] = 0
que.append((x1, y1))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while que:
	p = que.popleft()
	if (p[0] == x2) & (p[1] == y2):
		print(dp[x2][y2])
		return
	for i in range(4):
		for j in range(1, k + 1):
			nx = p[0] + dx[i] * j
			ny = p[1] + dy[i] * j
			if not (0 <= nx < h) & (0 <= ny < w):
				break
			if c[nx][ny] == '@':
				break
			if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:
				break
			if dp[nx][ny] == -1:
				que.append((nx, ny))
			dp[nx][ny] = dp[p[0]][p[1]] + 1
print(-1)


from collections import deque
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
c = list((list(input()) for _ in range(H)))
cost = [[H * W + 1] * W for _ in range(H)]
cost[x1 - 1][y1 - 1] = 0
queue = deque([[x1 - 1, y1 - 1]])
while queue:
	(x, y) = queue.popleft()
	for (vecx, vecy) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
		for k in range(1, K + 1):
			(nx, ny) = (x + k * vecx, y + k * vecy)
			if not 0 <= nx < H or not 0 <= ny < W:
				break
			if c[nx][ny] == '@':
				break
			if cost[nx][ny] > cost[x][y] + 1:
				cost[nx][ny] = cost[x][y] + 1
				queue.append([nx, ny])
			elif cost[nx][ny] < cost[x][y] + 1:
				break
if cost[x2 - 1][y2 - 1] == H * W + 1:
	print(-1)
else:
	print(cost[x2 - 1][y2 - 1])


(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())
raw = []
for _ in range(h):
	raw.append(input())
inf = 10 ** 6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0, x1, y1]]
while now:
	(s, x, y) = pop(now)
	if x == x2 and y == y2:
		print(s)
		exit()
	for i in range(1, k + 1):
		if x - i == -1 or raw[x - i][y] == '@' or seen[x - i][y] < s + 1:
			break
		if seen[x - i][y] != s + 1:
			seen[x - i][y] = s + 1
			push(now, [s + 1, x - i, y])
	for i in range(1, k + 1):
		if y - i == -1 or raw[x][y - i] == '@' or seen[x][y - i] < s + 1:
			break
		if seen[x][y - i] != s + 1:
			seen[x][y - i] = s + 1
			push(now, [s + 1, x, y - i])
	for i in range(1, k + 1):
		if x + i == h or raw[x + i][y] == '@' or seen[x + i][y] < s + 1:
			break
		if seen[x + i][y] != s + 1:
			seen[x + i][y] = s + 1
			push(now, [s + 1, x + i, y])
	for i in range(1, k + 1):
		if y + i == w or raw[x][y + i] == '@' or seen[x][y + i] < s + 1:
			break
		if seen[x][y + i] != s + 1:
			seen[x][y + i] = s + 1
			push(now, [s + 1, x, y + i])
print(-1)


from collections import deque
(n, m, k) = map(int, input().split())
(sx, sy, gx, gy) = map(int, input().split())
INF = float('inf')
d = [[INF] * m for _ in range(n)]
t = [[] for i in range(n)]
for i in range(n):
	a = list(input())
	t[i] = a
(sx, sy, gx, gy) = (sx - 1, sy - 1, gx - 1, gy - 1)

def bfs():
	que = deque()
	que.append((sx, sy))
	d[sx][sy] = 0
	while len(que):
		(x, y) = que.popleft()
		if x == gx and y == gy:
			break
		for (dx, dy) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
			for i in range(1, k + 1):
				(nx, ny) = (x + i * dx, y + i * dy)
				if not 0 <= nx < n or not 0 <= ny < m or t[nx][ny] != '.' or (d[nx][ny] <= d[x][y]):
					break
				elif d[nx][ny] > d[x][y] + 1:
					d[nx][ny] = d[x][y] + 1
					que.append((nx, ny))
	return d[gx][gy]
ans = bfs()
if ans == INF:
	print(-1)
else:
	print(ans)


from collections import deque
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
x1 -= 1
x2 -= 1
y1 -= 1
y2 -= 1
C = [list(input()) for _ in range(h)]
dist = [[10 ** 10] * w for _ in range(h)]
dist[x1][y1] = 0
que = deque([])
que.append((x1, y1))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while que:
	(a, b) = que.popleft()
	d = dist[a][b]
	if a == x2 and b == y2:
		print(dist[x2][y2])
		exit()
	for i in range(4):
		cx = a + dx[i]
		cy = b + dy[i]
		if cx < 0 or cx >= h or cy < 0 or (cy >= w):
			continue
		if C[cx][cy] == '@':
			continue
		for j in range(1, k + 1):
			nx = a + dx[i] * j
			ny = b + dy[i] * j
			if nx < 0 or nx >= h or ny < 0 or (ny >= w):
				break
			if C[nx][ny] == '@':
				break
			if dist[nx][ny] < d + 1:
				break
			if dist[nx][ny] == 10 ** 10:
				dist[nx][ny] = d + 1
				que.append((nx, ny))
print(-1)


import sys
from heapq import heapify, heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(H, W, K) = lr()
(SX, SY, GX, GY) = lr()
SX -= 1
SY -= 1
GX -= 1
GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10

def to_ID(x, y, con):
	return (x * W + y) * 4 + con

def mod_ceil_K(x):
	return (x + K - 1) // K * K

def push(d, id):
	if dist[id] < d:
		return
	dist[id] = d
	heappush(que, (d, id))
dist = [INF] * (H * W * 4)
start = to_ID(SX, SY, 0)
dist[start] = 0
que = [(0, start)]
UDLR = [(0, -1), (1, 0), (0, 1), (-1, 0)]
goal = to_ID(GX, GY, 0)
while que:
	(d, id) = heappop(que)
	if id == goal:
		answer = mod_ceil_K(d) // K
		print(answer)
		exit()
	if dist[id] < d:
		continue
	x = id // 4 // W
	y = id // 4 % W
	con = id % 4
	for i in range(4):
		next_id = to_ID(x, y, i)
		if dist[next_id] > mod_ceil_K(d):
			push(mod_ceil_K(d), next_id)
	dx = UDLR[con][0]
	dy = UDLR[con][1]
	nx = x + dx
	ny = y + dy
	if not (0 <= nx < H and 0 <= ny < W) or pond[nx][ny] == '@':
		continue
	next_id = to_ID(nx, ny, con)
	if dist[next_id] > d + 1:
		dist[next_id] = d + 1
		push(d + 1, next_id)
print(-1)


from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
(h, w, k) = map(int, readline().split())
(x1, y1, x2, y2) = map(int, readline().split())
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]
q = deque([(x1, y1)])
costs[x1][y1] = 0
while q:
	(x, y) = q.popleft()
	for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		for i in range(1, k + 1):
			(px, py) = (x + dx * i, y + dy * i)
			if not (0 <= px < h and 0 <= py < w) or field[px][py] == '@':
				break
			if 0 <= costs[px][py] < costs[x][y] + 1:
				break
			if costs[px][py] == -1:
				q.append((px, py))
			costs[px][py] = costs[x][y] + 1
print(costs[x2][y2])


def main():
	(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:
			exit(print(ans[x][y]))
		for (dx, dy) in [[1, 0], [-1, 0], [0, -1], [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)
main()


from heapq import heappop, heappush
from collections import deque

def dijkstra(xs, ys, xg, yg, h, w, k, field):
	inf = 1e+18
	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)

def __starting_point():
	main()
__starting_point()


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


def main():
	import sys
	from collections import deque
	input = sys.stdin.readline
	(h, w, k) = map(int, input().split())
	(sy, sx, gy, gx) = map(int, input().split())
	maze = [tuple(input()) for _ in range(h)]
	sy -= 1
	sx -= 1
	gy -= 1
	gx -= 1
	dis = [[-1] * w for _ in range(h)]
	dis[sy][sx] = 0
	d = deque([(sx, sy)])
	while len(d) > 0:
		(x, y) = d.popleft()
		if x == gx and y == gy:
			print(dis[gy][gx])
			exit()
		for (mx, my) in ((0, 1), (1, 0), (-1, 0), (0, -1)):
			for j in range(1, k + 1):
				nx = x + mx * j
				ny = y + my * j
				if 0 <= nx < w and 0 <= ny < h:
					if maze[ny][nx] == '.' and (dis[ny][nx] == -1 or dis[ny][nx] == dis[y][x] + 1):
						if dis[ny][nx] == -1:
							d.append((nx, ny))
						dis[ny][nx] = dis[y][x] + 1
					else:
						break
				else:
					break
	print(-1)
main()


from collections import deque
import sys
input = sys.stdin.readline
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = [input() for _ in range(h)]
ans = [[-1] * w for _ in range(h)]
ans[x1][y1] = 0
que = deque()
que.append((x1, y1))
direction = ((1, 0), (-1, 0), (0, -1), (0, 1))
while que:
	(x, y) = que.popleft()
	if x == x2 and y == y2:
		print(ans[x][y])
		return
	for (dx, dy) in direction:
		for i in range(1, k + 1):
			kx = x + dx * i
			ky = y + dy * i
			if not (0 <= kx < h and 0 <= ky < w) or dist[kx][ky] == '@':
				break
			if 0 <= ans[kx][ky] <= ans[x][y]:
				break
			if ans[kx][ky] == -1:
				que.append((kx, ky))
			ans[kx][ky] = ans[x][y] + 1
print(-1)


import sys

def input():
	return sys.stdin.readline()[:-1]
from collections import deque
(H, W, K) = map(int, input().split())
(sh, sw, gh, gw) = map(int, input().split())
c = ['@' * (W + 2)] + ['@' + input() + '@' for _ in range(H)] + ['@' * (W + 2)]
INF = 10 ** 6 + 5
dist = [[INF for _ in range(W + 2)] for _ in range(H + 2)]
dist[sh][sw] = 0
q = deque()
q.append(sh * (W + 2) + sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	(i, j) = (l // (W + 2), l % (W + 2))
	for (di, dj) in zip(DI, DJ):
		for k in range(1, K + 1):
			(ii, jj) = (i + di * k, j + dj * k)
			if c[ii][jj] == '@':
				break
			if dist[ii][jj] <= dist[i][j]:
				break
			if dist[ii][jj] > dist[i][j] + 1:
				dist[ii][jj] = dist[i][j] + 1
				if ii == gh and jj == gw:
					print(dist[ii][jj])
					sys.exit()
				q.append(ii * (W + 2) + jj)
print(-1)


(H, W, K) = list(map(int, input().split()))
(x1, y1, x2, y2) = [int(x) - 1 for x in input().split()]
pond = []
for _ in range(H):
	pond.append(list(input()))
inf = 10 ** 7
cost = [[inf] * W for _ in range(H)]
cost[x1][y1] = 0
from heapq import heapify, heappop, heappush
hq = [(0, x1, y1)]
while hq:
	(t, x, y) = heappop(hq)
	for i in range(1, K + 1):
		if x - i < 0 or pond[x - i][y] == '@' or cost[x - i][y] < t + 1:
			break
		if cost[x - i][y] > t + 1:
			cost[x - i][y] = t + 1
			heappush(hq, (t + 1, x - i, y))
	for i in range(1, K + 1):
		if y + i > W - 1 or pond[x][y + i] == '@' or cost[x][y + i] < t + 1:
			break
		if cost[x][y + i] > t + 1:
			cost[x][y + i] = t + 1
			heappush(hq, (t + 1, x, y + i))
	for i in range(1, K + 1):
		if x + i > H - 1 or pond[x + i][y] == '@' or cost[x + i][y] < t + 1:
			break
		if cost[x + i][y] > t + 1:
			cost[x + i][y] = t + 1
			heappush(hq, (t + 1, x + i, y))
	for i in range(1, K + 1):
		if y - i < 0 or pond[x][y - i] == '@' or cost[x][y - i] < t + 1:
			break
		if cost[x][y - i] > t + 1:
			cost[x][y - i] = t + 1
			heappush(hq, (t + 1, x, y - i))
if cost[x2][y2] == inf:
	print(-1)
	return
print(cost[x2][y2])


import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')

def main():
	(H, W, K) = map(int, readline().split())
	(x1, y1, x2, y2) = map(int, readline().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	C = read().split()
	dist = [[INF] * W for i in range(H)]
	dist[x1][y1] = 0
	d = deque([[x1, y1]])
	dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
	while d:
		(x, y) = d.popleft()
		if (x, y) == (x2, y2):
			print(dist[x][y])
			quit()
		for (dx, dy) in dxy:
			xx = x
			yy = y
			for i in range(K):
				xx += dx
				yy += dy
				if 0 <= xx < H and 0 <= yy < W and (C[xx][yy] != '@'):
					if dist[xx][yy] <= dist[x][y]:
						break
					if dist[xx][yy] == INF:
						d.append([xx, yy])
					dist[xx][yy] = dist[x][y] + 1
				else:
					break
	print(-1)
main()


def main():
	import sys
	input = sys.stdin.readline
	(h, w, k) = map(int, input().split())
	(sx, sy, tx, ty) = map(int, input().split())
	b = [[-1] * (w + 2)]
	for i in range(h):
		s = input()
		bb = [-1]
		for j in s:
			if j == '.':
				bb.append(0)
			else:
				bb.append(-1)
		bb.append(-1)
		b.append(bb)
	b.append([-1] * (w + 2))
	d = []
	d.append((sx, sy))
	for ss in d:
		(x, y) = ss
		if x == tx and y == ty:
			print(b[x][y])
			return
		for i in range(1, k + 1):
			if b[x + i][y] <= b[x][y] and b[x + i][y] != 0:
				break
			if b[x + i][y] == 0:
				d.append((x + i, y))
			b[x + i][y] = b[x][y] + 1
		for i in range(1, k + 1):
			if b[x - i][y] <= b[x][y] and b[x - i][y] != 0:
				break
			if b[x - i][y] == 0:
				d.append((x - i, y))
			b[x - i][y] = b[x][y] + 1
		for j in range(1, k + 1):
			if b[x][y + j] <= b[x][y] and b[x][y + j] != 0:
				break
			if b[x][y + j] == 0:
				d.append((x, y + j))
			b[x][y + j] = b[x][y] + 1
		for j in range(1, k + 1):
			if b[x][y - j] <= b[x][y] and b[x][y - j] != 0:
				break
			if b[x][y - j] == 0:
				d.append((x, y - j))
			b[x][y - j] = b[x][y] + 1
	print(-1)

def __starting_point():
	main()
__starting_point()


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

def solve():
	(H, W, K) = map(int, input().split())
	(y1, x1, y2, x2) = map(int, input().split())
	l = [[1 if s == '@' else 0 for s in input()] for _ in range(H)]
	INF = 10 ** 12
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	ddy = [0, 0, -1, 1]
	ddx = [-1, 1, 0, 0]
	dist = defaultdict(lambda : INF)
	dist[y1, x1] = 0
	q = deque([(y1, x1)])
	while q:
		(y, x) = q.popleft()
		for (dy, dx) in zip(ddy, ddx):
			for j in range(1, K + 1):
				if not (0 <= y + dy * j < H and 0 <= x + dx * j < W) or l[y + dy * j][x + dx * j] or dist[y + dy * j, x + dx * j] < dist[y, x] + 1:
					break
				if dist[y + dy * j, x + dx * j] > dist[y, x] + 1:
					dist[y + dy * j, x + dx * j] = dist[y, x] + 1
					q.append((y + dy * j, x + dx * j))
				else:
					continue
	ans = dist[y2, x2]
	print(ans if ans != INF else -1)
solve()


import sys
from collections import deque
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(H, W, K) = lr()
(SX, SY, GX, GY) = lr()
SX -= 1
SY -= 1
GX -= 1
GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10
dist = [[INF] * W for _ in range(H)]
dist[SX][SY] = 0
que = deque([(0, SX, SY)])
UDLR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
	(d, px, py) = que.popleft()
	if px == GX and py == GY:
		print(d)
		exit()
	if dist[px][py] < d:
		continue
	nd = d + 1
	for (dx, dy) in UDLR:
		nx = px + dx
		ny = py + dy
		for _ in range(K):
			if not 0 <= nx < H or not 0 <= ny < W or dist[nx][ny] < nd or (pond[nx][ny] == '@'):
				break
			if dist[nx][ny] > nd:
				que.append((nd, nx, ny))
				dist[nx][ny] = nd
			nx += dx
			ny += dy
print(-1)


def ii():
	return int(input())

def iim():
	return list(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))


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 = [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)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
(h, w, k) = map(int, readline().split())
(x1, y1, x2, y2) = map(int, readline().split())
c = read().split()
inf = 10 ** 7
cost = [[inf] * (w + 2) for _ in range(h + 2)]
for i in range(h):
	for j in range(w):
		if c[i][j] == '@':
			cost[i + 1][j + 1] = -1
for i in range(h + 2):
	cost[i][0] = -1
	cost[i][-1] = -1
for j in range(w + 2):
	cost[0][j] = -1
	cost[-1][j] = -1
cost[x1][y1] = 0
stack = [(x1, y1)]
cnt = 0
while stack:
	cnt += 1
	next = set()
	while stack:
		(x, y) = stack.pop()
		for (dx, dy) in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
			for j in range(1, k + 1):
				jx = x + dx * j
				jy = y + dy * j
				if cost[jx][jy] < cnt:
					break
				next.add((jx, jy))
	for (jx, jy) in next:
		cost[jx][jy] = cnt
		stack.append((jx, jy))
if cost[x2][y2] == inf:
	print(-1)
else:
	print(cost[x2][y2])


import collections
(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] * w for _ in range(h)]
checked[sy][sx] = 1
cost = [[10 ** 18] * w for _ in range(h)]
cost[sy][sx] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while len(q) != 0:
	(x, y) = q.popleft()
	c = cost[y][x]
	for i in range(4):
		for j in range(1, k + 1):
			if x + j * dx[i] < 0 or w <= x + j * dx[i] or y + j * dy[i] < 0 or (h <= y + j * dy[i]):
				break
			if board[y + j * dy[i]][x + j * dx[i]] == '@':
				break
			if cost[y + j * dy[i]][x + j * dx[i]] <= c:
				break
			if cost[y + j * dy[i]][x + j * dx[i]] > c + 1:
				q.append((x + j * dx[i], y + j * dy[i]))
				cost[y + j * dy[i]][x + j * dx[i]] = c + 1
if cost[gy][gx] == 10 ** 18:
	print(-1)
else:
	print(cost[gy][gx])


import queue
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
li = [list(input()) for _ in range(H)]
cnt = [[10 ** 10 for _ in range(W)] for _ in range(H)]
cnt2 = [[10 ** 10 for _ in range(W)] for _ in range(H)]
xy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = queue.Queue()
q.put([x1 - 1, y1 - 1, 0])
cnt[x1 - 1][y1 - 1] = 0
while not q.empty():
	mm = q.get()
	x = mm[0]
	y = mm[1]
	cst = mm[2]
	for i in range(4):
		for j in range(1, K + 1):
			nx = x + xy[i][0] * j
			ny = y + xy[i][1] * j
			if nx >= 0 and nx < H and (ny >= 0) and (ny < W) and (li[nx][ny] == '.'):
				if cnt[nx][ny] != 10 ** 10 and cnt[nx][ny] < cst + 1:
					break
				elif cnt[nx][ny] != 10 ** 10:
					continue
				else:
					cnt[nx][ny] = cst + 1
					q.put([nx, ny, cst + 1])
			else:
				break
if cnt[x2 - 1][y2 - 1] == 10 ** 10:
	print(-1)
else:
	print(cnt[x2 - 1][y2 - 1])


from collections import deque

def bfs(visited, sy, sx, gy, gx):
	queue = deque([[sy, sx]])
	visited[sy][sx] = 0
	while queue:
		(y, x) = queue.popleft()
		if [y, x] == [gy, gx]:
			return visited[y][x]
		for (dx, dy) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			for k in range(1, K + 1):
				new_x = x + dx * k
				new_y = y + dy * k
				if 0 <= new_y < H and 0 <= new_x < W:
					if m[new_y][new_x] == '@':
						break
					elif visited[new_y][new_x] == -1:
						visited[new_y][new_x] = visited[y][x] + 1
						queue.append([new_y, new_x])
					elif visited[new_y][new_x] < visited[y][x] + 1:
						break
				else:
					break
(H, W, K) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
m = []
for i in range(H):
	m.append(str(input()))
visited = [[-1] * W for i in range(H)]
bfs(visited, x1, y1, x2, y2)
print(visited[x2][y2])


from collections import deque
(H, W, K) = list(map(int, input().split()))
(sx, sy, tx, ty) = [int(a) - 1 for a in input().split()]
INF = 10 ** 18
A = [input() for _ in range(H)]
minDist = [[INF] * W for _ in range(H)]
minDist[sx][sy] = 0
que = deque([(0, sx, sy)])
while que:
	(dist, nx, ny) = que.popleft()
	for i in range(1, K + 1):
		if nx + i >= H:
			break
		if minDist[nx + i][ny] <= dist or A[nx + i][ny] == '@':
			break
		if minDist[nx + i][ny] > dist + 1:
			minDist[nx + i][ny] = dist + 1
			que.append((dist + 1, nx + i, ny))
	for i in range(1, K + 1):
		if nx - i < 0:
			break
		if minDist[nx - i][ny] <= dist or A[nx - i][ny] == '@':
			break
		if minDist[nx - i][ny] > dist + 1:
			minDist[nx - i][ny] = dist + 1
			que.append((dist + 1, nx - i, ny))
	for i in range(1, K + 1):
		if ny + i >= W:
			break
		if minDist[nx][ny + i] <= dist or A[nx][ny + i] == '@':
			break
		if minDist[nx][ny + i] > dist + 1:
			minDist[nx][ny + i] = dist + 1
			que.append((dist + 1, nx, ny + i))
	for i in range(1, K + 1):
		if ny - i < 0:
			break
		if minDist[nx][ny - i] <= dist or A[nx][ny - i] == '@':
			break
		if minDist[nx][ny - i] > dist + 1:
			minDist[nx][ny - i] = dist + 1
			que.append((dist + 1, nx, ny - i))
ans = minDist[tx][ty]
print(ans if ans < INF else -1)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random, resource
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	(h, w, k) = LI()
	(y1, x1, y2, x2) = LI_()
	ca = [S() for _ in range(h)]
	aa = [[-1 if c == '@' else inf for c in s] for s in ca]
	aa[y1][x1] = 0
	q = [(y1, x1)]
	v = collections.defaultdict(bool)
	t = 0
	while q:
		t += 1
		nq = []
		for (y, x) in q:
			for (dy, dx) in dd:
				for i in range(1, k + 1):
					ty = y + dy * i
					tx = x + dx * i
					if ty < 0 or ty >= h or tx < 0 or (tx >= w) or (aa[ty][tx] < t):
						break
					if aa[ty][tx] == t:
						continue
					aa[ty][tx] = t
					nq.append((ty, tx))
		q = nq
	if aa[y2][x2] == inf:
		return -1
	return aa[y2][x2]
print(main())


from heapq import heappop, heappush
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())
S = [input()[:-1] for _ in [0] * H]

def geth(x, y, z):
	return (x * W + y) * 4 + z

def push(x, y, z, d):
	h = geth(x, y, z)
	if D[h] <= d:
		return
	D[h] = d
	heappush(q, (d, h))
INF = 10 ** 10
MAX = H * W * 4
D = [INF] * MAX
dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
q = []
for z in range(4):
	heappush(q, (0, geth(x1, y1, z)))
while q:
	(d, h) = heappop(q)
	z = h % 4
	(x, y) = divmod(h // 4, W)
	if d > D[h]:
		continue
	D[h] = d
	for (_z, (dx, dy)) in enumerate(dirs):
		if _z == z:
			(_x, _y) = (x + dx, y + dy)
			if 0 <= _x < H and 0 <= _y < W and (S[_x][_y] == '.'):
				push(_x, _y, z, d + 1)
		else:
			_h = geth(x, y, _z)
			_d = (d + K - 1) // K * K
			push(x, y, _z, _d)
g = geth(x2, y2, 0)
ans = min(D[g:g + 4])
if ans == INF:
	print(-1)
else:
	ans = (ans - 1 + K) // K
	print(ans)


import pprint
(H, W, K) = map(int, input().split())
import copy
(x1, y1, x2, y2) = map(int, input().split())
lastraw = ['@'] * (W + 2)
field = [['@'] * (W + 2)]
for i in range(H):
	field.append(['@'] + list(input()) + ['@'])
field.append(lastraw)
goal_point = (y2, x2)
[sy, sx] = [y1, x1]
[gy, gx] = [y2, x2]
field[x1][y1] = 0
queue = [[sy, sx]]
tests = ((-1, 0), (0, 1), (1, 0), (0, -1))
moves = 0
while True:
	if len(queue) == 0:
		moves = -1
		break
	queue_next = []
	moves += 1
	for (y, x) in queue:
		for (ny, nx) in tests:
			(ty, tx) = (y + ny, x + nx)
			if field[tx][ty] == '.':
				field[tx][ty] = moves
				queue_next.append((ty, tx))
				for i in range(K - 1):
					(ty, tx) = (ty + ny, tx + nx)
					if field[tx][ty] == '.':
						field[tx][ty] = moves
						queue_next.append((ty, tx))
					elif field[tx][ty] == moves:
						pass
					else:
						break
			elif field[tx][ty] == moves:
				for i in range(K - 1):
					(ty, tx) = (ty + ny, tx + nx)
					if field[tx][ty] == '.':
						field[tx][ty] = moves
						queue_next.append((ty, tx))
					elif field[tx][ty] == moves:
						pass
					else:
						break
	queue = queue_next
	if goal_point in queue:
		break
print(moves)


from collections import deque
INF = 10 ** 18
(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)]
queue = deque()
queue.append((x1, y1))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
dist = [[INF for j in range(W)] for i in range(H)]
dist[x1][y1] = 0
while queue:
	(x, y) = queue.popleft()
	for i in range(4):
		for k in range(K):
			nx = x + (k + 1) * dx[i]
			ny = y + (k + 1) * dy[i]
			if not (0 <= nx < H and 0 <= ny < W):
				break
			if C[nx][ny] == '@':
				break
			if dist[nx][ny] <= dist[x][y]:
				break
			if dist[nx][ny] != INF:
				continue
			dist[nx][ny] = dist[x][y] + 1
			queue.append((nx, ny))
print(dist[x2][y2] if dist[x2][y2] != INF else -1)


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


import sys
input = sys.stdin.readline
(H, W, K) = map(int, input().rstrip().split())
(x1, y1, x2, y2) = map(int, input().split())
c = [input().rstrip() for i in range(H)]
s = W * (x1 - 1) + y1 - 1
g = W * (x2 - 1) + y2 - 1
import heapq
que = []
d = [float('inf')] * (4 * H * W)
d[4 * s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4 * s))
while len(que) != 0:
	(cost, v) = heapq.heappop(que)
	if d[v] < cost:
		continue
	for j in range(4):
		nv = v - v % 4 + (v % 4 + j) % 4
		if d[nv] > d[v] - d[v] % K + K * (d[v] % K > 0):
			d[nv] = d[v] - d[v] % K + K * (d[v] % K > 0)
			heapq.heappush(que, (d[nv], nv))
	i = v // 4
	(h, w) = (i // W, i % W)
	if v % 4 == 0:
		if h != 0 and c[h - 1][w] == '.':
			if d[v - 4 * W] > d[v] + 1:
				d[v - 4 * W] = d[v] + 1
				heapq.heappush(que, (d[v - 4 * W], v - 4 * W))
	elif v % 4 == 2:
		if h != H - 1 and c[h + 1][w] == '.':
			if d[v + 4 * W] > d[v] + 1:
				d[v + 4 * W] = d[v] + 1
				heapq.heappush(que, (d[v + 4 * W], v + 4 * W))
	elif v % 4 == 1:
		if w != W - 1 and c[h][w + 1] == '.':
			if d[v + 4] > d[v] + 1:
				d[v + 4] = d[v] + 1
				heapq.heappush(que, (d[v + 4], v + 4))
	elif w != 0 and c[h][w - 1] == '.':
		if d[v - 4] > d[v] + 1:
			d[v - 4] = d[v] + 1
			heapq.heappush(que, (d[v - 4], v - 4))
ans = d[4 * g]
if ans >= 10 ** 15:
	print(-1)
else:
	print(ans // K + (ans % K > 0))


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


from collections import deque
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
c = [input().rstrip() for _ in range(H)]
d = deque([(x1 - 1, y1 - 1)])
dp = [[-1] * W for _ in range(H)]
dp[x1 - 1][y1 - 1] = 0
while d:
	(x, y) = d.popleft()
	if x == x2 - 1 and y == y2 - 1:
		print(dp[x][y])
		break
	for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		for i in range(1, K + 1):
			nx = x + dx * i
			ny = y + dy * i
			if 0 > nx or nx >= H or 0 > ny or (ny >= W) or (c[nx][ny] == '@'):
				break
			if dp[nx][ny] == -1:
				dp[nx][ny] = dp[x][y] + 1
				d.append((nx, ny))
			elif dp[nx][ny] <= dp[x][y]:
				break
else:
	print(-1)


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


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 = input()
		l = ['@']
		for j in i:
			l.append(j)
		l.append('@')
		c.append(l)
	c.append(['@'] * (w + 2))
	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] != -1:
			if (seen[xi][yi] + k - 1) // k * k > cost:
				(xj, yj) = (xi + dx[direction], yi + dy[direction])
				if c[xj][yj] == '.':
					heapq.heappush(todo, (cost + 1, xj, yj, direction))
			continue
		seen[xi][yi] = cost
		if xi == x2 and yi == y2:
			print((cost + k - 1) // k)
			return
		for j in range(4):
			(xj, yj) = (xi + dx[j], yi + dy[j])
			if c[xj][yj] == '.':
				if j == direction:
					if seen[xj][yj] == -1 or (seen[xj][yj] + k - 1) // k * k > cost:
						heapq.heappush(todo, (cost + 1, xj, yj, j))
				elif seen[xj][yj] == -1:
					heapq.heappush(todo, ((cost + k - 1) // k * k + 1, xj, yj, j))
	print(-1)
main()


import sys
import collections
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def main():
	(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)]
	q = collections.deque()
	q.append((X1 - 1, Y1 - 1, 0))
	V = [[float('inf')] * W for j in range(H)]
	V[X1 - 1][Y1 - 1] = 0
	while q:
		c = q.popleft()
		x = c[0]
		y = c[1]
		d = c[2]
		if y == Y2 - 1 and x == X2 - 1:
			print(c[2])
			return
		(e, w, n, s) = (True, True, True, True)
		for k in range(1, K + 1):
			if not e and (not w) and (not n) and (not s):
				break
			if e:
				if y + k >= W or C[x][y + k] == '@':
					e = False
				else:
					if V[x][y + k] == float('inf'):
						V[x][y + k] = d + 1
						q.append((x, y + k, d + 1))
					if V[x][y + k] < d + 1:
						e = False
			if w:
				if y - k < 0 or C[x][y - k] == '@':
					w = False
				else:
					if V[x][y - k] == float('inf'):
						V[x][y - k] = d + 1
						q.append((x, y - k, d + 1))
					if V[x][y - k] < d + 1:
						w = False
			if n:
				if x - k < 0 or C[x - k][y] == '@':
					n = False
				else:
					if V[x - k][y] == float('inf'):
						V[x - k][y] = d + 1
						q.append((x - k, y, d + 1))
					if V[x - k][y] < d + 1:
						n = False
			if s:
				if x + k >= H or C[x + k][y] == '@':
					s = False
				else:
					if V[x + k][y] == float('inf'):
						V[x + k][y] = d + 1
						q.append((x + k, y, d + 1))
					if V[x + k][y] < d + 1:
						s = False
	print(-1)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque
INF = float('inf')

def resolve():
	(H, W, K) = map(int, input().split())
	(sx, sy, gx, gy) = map(lambda x: int(x) - 1, input().split())
	G = [list(input()) for _ in range(H)]
	dist = [[INF] * W for i in range(H)]
	dist[sx][sy] = 0
	q = deque([(sx, sy)])
	drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
	while q:
		(x, y) = q.popleft()
		if (x, y) == (gx, gy):
			print(dist[x][y])
			return
		for (dx, dy) in drc:
			nx = x
			ny = y
			for k in range(K):
				nx += dx
				ny += dy
				if 0 <= nx < H and 0 <= ny < W and (G[nx][ny] != '@'):
					if dist[nx][ny] <= dist[x][y]:
						break
					if dist[nx][ny] == INF:
						q.append((nx, ny))
					dist[nx][ny] = dist[x][y] + 1
				else:
					break
	print(-1)
resolve()


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


from collections import deque
dxdy = ((-1, 0), (1, 0), (0, -1), (0, 1))
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
mp = [input() for _ in range(H)]
INF = 10 ** 10
dist = [[INF] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = deque()
q.append((x1 - 1, y1 - 1))
while q:
	(x, y) = q.popleft()
	if x == x2 - 1 and y == y2 - 1:
		print(dist[x2 - 1][y2 - 1])
		exit()
	else:
		for (dx, dy) in dxdy:
			for i in range(1, K + 1):
				nx = x + dx * i
				ny = y + dy * i
				if not (0 <= nx < H and 0 <= ny < W) or mp[nx][ny] == '@':
					break
				if dist[nx][ny] <= dist[x][y]:
					break
				if dist[nx][ny] == INF:
					q.append((nx, ny))
					dist[nx][ny] = dist[x][y] + 1
print(-1)


def ii():
	return int(input())

def iim():
	return list(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))


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)


(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
import sys
input = sys.stdin.readline
L = []
l = ['@' for i in range(W + 2)]
L.append(l)
for i in range(H):
	c = ['@'] + list(input().rstrip()) + ['@']
	L.append(c)
L.append(l)
L[x1][y1] = 0
Q = [[x1, y1]]
for i in range(10 ** 7):
	if i >= len(Q):
		break
	for j in range(1, K + 1):
		if L[Q[i][0] + j][Q[i][1]] == '.':
			L[Q[i][0] + j][Q[i][1]] = L[Q[i][0]][Q[i][1]] + 1
			Q.append([Q[i][0] + j, Q[i][1]])
		elif L[Q[i][0] + j][Q[i][1]] == L[Q[i][0]][Q[i][1]] + 1:
			continue
		else:
			break
	for j in range(1, K + 1):
		if L[Q[i][0] - j][Q[i][1]] == '.':
			L[Q[i][0] - j][Q[i][1]] = L[Q[i][0]][Q[i][1]] + 1
			Q.append([Q[i][0] - j, Q[i][1]])
		elif L[Q[i][0] - j][Q[i][1]] == L[Q[i][0]][Q[i][1]] + 1:
			continue
		else:
			break
	for j in range(1, K + 1):
		if L[Q[i][0]][Q[i][1] + j] == '.':
			L[Q[i][0]][Q[i][1] + j] = L[Q[i][0]][Q[i][1]] + 1
			Q.append([Q[i][0], Q[i][1] + j])
		elif L[Q[i][0]][Q[i][1] + j] == L[Q[i][0]][Q[i][1]] + 1:
			continue
		else:
			break
	for j in range(1, K + 1):
		if L[Q[i][0]][Q[i][1] - j] == '.':
			L[Q[i][0]][Q[i][1] - j] = L[Q[i][0]][Q[i][1]] + 1
			Q.append([Q[i][0], Q[i][1] - j])
		elif L[Q[i][0]][Q[i][1] - j] == L[Q[i][0]][Q[i][1]] + 1:
			continue
		else:
			break
if L[x2][y2] == '.':
	print(-1)
else:
	print(L[x2][y2])


from collections import deque
(h, w, k) = map(int, input().split())
(y1, x1, y2, x2) = map(int, input().split())
c = []
for _ in range(h):
	c.append(input())
q = deque([(x1 - 1, y1 - 1)])
dxdy = [(-1, 0), (0, -1), (0, 1), (1, 0)]
dist = [[1000000] * w for _ in range(h)]
dist[y1 - 1][x1 - 1] = 0
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 < w and 0 <= y + dy < h):
				break
			if c[y + dy][x + dx] == '@' or dist[y + dy][x + dx] <= dist[y][x]:
				break
			if x + dx == x2 - 1 and y + dy == y2 - 1:
				print(dist[y][x] + 1)
				exit(0)
			if dist[y + dy][x + dx] > dist[y][x] + 1:
				dist[y + dy][x + dx] = dist[y][x] + 1
				q.append((x + dx, y + dy))
print(-1)


from collections import deque
import sys

def bfs(M, sy, sx):
	queue = deque([[xs, ys]])
	M[sy][sx] = 0
	while queue:
		(x1, y1) = queue.popleft()
		if [x1, y1] == [xg, yg]:
			return M[x1][y1]
		for (dx, dy) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			for k in range(1, K + 1):
				new_x = x1 + dx * k
				new_y = y1 + dy * k
				if 0 <= new_x < H and 0 <= new_y < W:
					if m[new_x][new_y] == '@':
						break
					elif M[new_x][new_y] == -1:
						M[new_x][new_y] = M[x1][y1] + 1
						queue.append([new_x, new_y])
					elif M[new_x][new_y] < M[x1][y1] + 1:
						break
				else:
					break
(H, W, K) = list(map(int, input().split()))
(xs, ys, xg, yg) = list(map(int, input().split()))
(xs, ys, xg, yg) = (xs - 1, ys - 1, xg - 1, yg - 1)
m = []
for i in range(H):
	m.append(list(map(str, sys.stdin.readline().strip())))
M = [[-1] * W for i in range(H)]
bfs(M, xs, ys)
print(M[xg][yg])


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)

def __starting_point():
	main()
__starting_point()


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)


(h, w, k) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
m = [[-1] * w for _ in range(h)]
for hh in range(h):
	c = input()
	for (ww, cc) in enumerate(c):
		if cc == '.':
			m[hh][ww] = h * w
from collections import deque
q = deque()
q.append((0, x1, y1))
while q:
	(s, x, y) = q.popleft()
	s1 = s + 1
	for i in range(1, k + 1):
		(xx, yy) = (x + i, y)
		if xx >= h or m[xx][yy] <= s:
			break
		if m[xx][yy] == s1:
			continue
		if xx == x2 and yy == y2:
			print(s1)
			return
		m[xx][yy] = s1
		q.append((s1, xx, yy))
	for i in range(1, k + 1):
		(xx, yy) = (x - i, y)
		if xx < 0 or m[xx][yy] <= s:
			break
		if m[xx][yy] == s1:
			continue
		if xx == x2 and yy == y2:
			print(s1)
			return
		m[xx][yy] = s1
		q.append((s1, xx, yy))
	for i in range(1, k + 1):
		(xx, yy) = (x, y + i)
		if yy >= w or m[xx][yy] <= s:
			break
		if m[xx][yy] == s1:
			continue
		if xx == x2 and yy == y2:
			print(s1)
			return
		m[xx][yy] = s1
		q.append((s1, xx, yy))
	for i in range(1, k + 1):
		(xx, yy) = (x, y - i)
		if yy < 0 or m[xx][yy] <= s:
			break
		if m[xx][yy] == s1:
			continue
		if xx == x2 and yy == y2:
			print(s1)
			return
		m[xx][yy] = s1
		q.append((s1, xx, yy))
print(-1)


import sys
from collections import deque
readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : list(map(int, readline().split()))
nl = lambda : list(map(int, readline().split()))

def solve():
	(h, w, k) = nm()
	(sy, sx, gy, gx) = nm()
	d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
	sx -= 1
	sy -= 1
	gx -= 1
	gy -= 1
	C = [ns() for _ in range(h)]
	G = [[10 ** 7] * w for _ in range(h)]
	G[sy][sx] = 0
	q = deque([(sy, sx)])
	while q:
		(y, x) = q.popleft()
		for i in range(4):
			(dy, dx) = d[i]
			(ny, nx) = (y, x)
			for _ in range(k):
				ny += dy
				nx += dx
				if ny < 0 or h <= ny or nx < 0 or (w <= nx):
					break
				if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
					break
				if G[ny][nx] > G[y][x] + 1:
					G[ny][nx] = G[y][x] + 1
					q.append((ny, nx))
	ans = G[gy][gx]
	print(ans if ans < 10 ** 7 else -1)
	return
solve()


import sys
input = sys.stdin.readline
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())
	v1 = x1 * (w + 1) + y1
	v2 = x2 * (w + 1) + y2
	C = ''.join((input().rstrip() + '@' for _ in range(h)))
	dist = [-1 if c == '@' else 10 ** 10 for c in C]
	ans = 0
	que = deque()
	que.append(v1)
	dist[v1] = 0
	while que:
		v = que.popleft()
		if v == v2:
			print(dist[v2])
			exit()
		d = dist[v] + 1
		for dr in (-(w + 1), -1, w + 1, 1):
			for i in range(1, k + 1):
				nv = v + dr * i
				if 0 <= nv < h * (w + 1):
					if dist[nv] > d:
						dist[nv] = d
						que.append(nv)
					elif dist[nv] == d:
						continue
					else:
						break
				else:
					break
	print(-1)
main()


def main():
	from collections import deque
	import sys
	input = lambda : sys.stdin.readline().rstrip()
	if 'get_ipython' in globals():
		(h, w, k) = (3, 5, 2)
		(x1, y1, x2, y2) = (3, 2, 3, 4)
		dist = ['.....', '.@..@', '..@..']
	else:
		(h, w, k) = map(int, input().split())
		(x1, y1, x2, y2) = map(int, input().split())
		dist = [input() for _ in range(h)]
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	ans = [[-1] * w for _ in range(h)]
	ans[x1][y1] = 0
	que = deque()
	que.append((x1, y1))
	direction = ((1, 0), (-1, 0), (0, -1), (0, 1))
	while que:
		(x, y) = que.popleft()
		if x == x2 and y == y2:
			print(ans[x][y])
			return
		for (dx, dy) in direction:
			for i in range(1, k + 1):
				kx = x + dx * i
				ky = y + dy * i
				if not (0 <= kx < h and 0 <= ky < w) or dist[kx][ky] == '@':
					break
				if 0 <= ans[kx][ky] <= ans[x][y]:
					break
				if ans[kx][ky] == -1:
					que.append((kx, ky))
				ans[kx][ky] = ans[x][y] + 1
	print(-1)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())
s = [None] * h
for i in range(h):
	s[i] = input()
from queue import deque
q0 = deque([(0, x1, y1, (0, 0), 0)])
q1 = deque()
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dist = [None] * (w * h)
dist[x1 * w + y1] = 0
done = [0] * (w * h)
done[x1 * w + y1] = 15
while q0 or q1:
	if not q0:
		q0 = q1
		q1 = deque()
	(d, x, y, t, td) = q0.popleft()
	for (i, (xx, yy)) in enumerate(zip(dx, dy)):
		if (-xx, -yy) == t:
			continue
		(nx, ny) = (xx + x, yy + y)
		if nx < 0 or nx >= h or ny < 0 or (ny >= w) or (s[nx][ny] == '@'):
			continue
		if (xx, yy) == t and td < k:
			nd = d
			ntd = td + 1
			q = q0
		else:
			nd = d + 1
			ntd = 1
			q = q1
		if dist[nx * w + ny] is None or nd < dist[nx * w + ny]:
			q.append((nd, nx, ny, (xx, yy), ntd))
			dist[nx * w + ny] = nd
			done[nx * w + ny] = 1 << i
		elif nd == dist[nx * w + ny] and done[nx * w + ny] & 1 << i == 0:
			q.append((nd, nx, ny, (xx, yy), ntd))
			done[nx * w + ny] |= 1 << i
if dist[x2 * w + y2] is None:
	print(-1)
else:
	print(dist[x2 * w + y2])


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
from collections import deque

def resolve():
	(m, n, k) = map(int, input().split())
	(si, sj, ti, tj) = map(lambda x: int(x) - 1, input().split())
	grid = [input() for _ in range(m)]
	dist = [[INF] * n for _ in range(m)]
	dist[si][sj] = 0
	D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	queue = deque([(si, sj)])
	while queue:
		(i, j) = queue.popleft()
		for (di, dj) in D:
			for s in range(1, k + 1):
				(ni, nj) = (i + s * di, j + s * dj)
				if not (0 <= ni < m and 0 <= nj < n):
					break
				if grid[ni][nj] == '@':
					break
				if dist[ni][nj] <= dist[i][j]:
					break
				if dist[ni][nj] > dist[i][j] + 1:
					dist[ni][nj] = dist[i][j] + 1
					queue.append((ni, nj))
	ans = dist[ti][tj]
	if ans == INF:
		ans = -1
	print(ans)
resolve()


import collections
(H, W, K) = map(int, input().split())
(s1, e1, s2, e2) = map(int, input().split())
s1 -= 1
e1 -= 1
s2 -= 1
e2 -= 1
L = []
board = []
for _ in range(H):
	a = input()
	L.append(a)
for i in range(H):
	l = L[i]
	tmp = []
	for j in range(len(l)):
		tmp.append(l[j])
	board.append(tmp)
queue = collections.deque()
queue.append([0, s1, e1])
seen = [[float('inf')] * W for _ in range(H)]
destination = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
	(cost, x, y) = queue.popleft()
	seen[x][y] = cost
	if x == s2 and y == e2:
		print(cost)
		exit()
		break
	for (dx, dy) in destination:
		(X, Y) = (x, y)
		for i in range(1, K + 1):
			NX = X + i * dx
			NY = Y + i * dy
			if 0 > NX or NX >= H or 0 > NY or (NY >= W) or (seen[NX][NY] < seen[X][Y] + 1):
				break
			elif board[NX][NY] == '@':
				break
			elif seen[NX][NY] == float('inf'):
				queue.append([cost + 1, NX, NY])
				seen[NX][NY] = cost + 1
print(-1)


import sys
from collections import deque
input = iter(sys.stdin.readlines()).__next__
(R, C, K) = [int(x) for x in input().split()]
(X1, Y1, X2, Y2) = [int(x) - 1 for x in input().split()]
grid = [input().rstrip() for r in range(R)]
source = (X1, Y1)
q = deque([source])
dist = {source: 0}

def getNbr(node, currDist):
	(r, c) = node
	ret = []
	for (dr, dc) in [(0, 0), (-1, 0), (0, -1), (0, 1), (1, 0)]:
		for k in range(1, K + 1):
			nr = r + dr * k
			nc = c + dc * k
			if not (0 <= nr < R and 0 <= nc < C):
				break
			if grid[nr][nc] == '@' or ((nr, nc) in dist and dist[nr, nc] <= d):
				break
			ret.append((nr, nc))
	return ret
while q:
	node = q.popleft()
	d = dist[node]
	for nbr in getNbr(node, d):
		if nbr not in dist:
			q.append(nbr)
			dist[nbr] = d + 1
if False:
	for row in grid:
		print(row)
	print()
	for r in range(R):
		for c in range(C):
			print(dist.get((r, c), '?'), end=' ')
		print()
if (X2, Y2) in dist:
	print(dist[X2, Y2])
else:
	print(-1)


import sys
from collections import deque
input = sys.stdin.buffer.readline
(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 = [list(input()) for i in range(h)]
pq = [0] * (h * w)
dp = [10 ** 7] * (h * w)
pq[x1 * w + y1] = 3
dp[x1 * w + y1] = 0
tank = deque([x1 * w + y1])
while tank:
	now = tank.popleft()
	cost = dp[now]
	for i in range(1, k + 1):
		if (now + i) % w != 0 and dp[now + i] > cost and (c[(now + i) // w][(now + i) % w] == 46) and (pq[now + i] < 5):
			pq[now + i] += 1
			dp[now + i] = cost + 1
			tank.append(now + i)
		else:
			break
	for i in range(1, k + 1):
		if (now - i) % w != w - 1 and dp[now - i] > cost and (c[(now - i) // w][(now - i) % w] == 46) and (pq[now - i] < 5):
			pq[now - i] += 1
			dp[now - i] = cost + 1
			tank.append(now - i)
		else:
			break
	for i in range(1, k + 1):
		if now + i * w < h * w and dp[now + i * w] > cost and (c[(now + i * w) // w][(now + i * w) % w] == 46) and (pq[now + i * w] < 5):
			pq[now + i * w] += 1
			dp[now + i * w] = cost + 1
			tank.append(now + i * w)
		else:
			break
	for i in range(1, k + 1):
		if now - i * w >= 0 and dp[now - i * w] > cost and (c[(now - i * w) // w][(now - i * w) % w] == 46) and (pq[now - i * w] < 5):
			pq[now - i * w] += 1
			dp[now - i * w] = cost + 1
			tank.append(now - i * w)
		else:
			break
if dp[x2 * w + y2] == 10 ** 7:
	print(-1)
else:
	print(dp[x2 * w + y2])


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


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


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


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)


from collections import deque
(H, W, K) = map(int, input().split())
(sh, sw, gh, gw) = map(int, input().split())
(sh, sw, gh, gw) = (sh - 1, sw - 1, gh - 1, gw - 1)
G = [list(input()) for _ in range(H)]
INF = 10 ** 9
D = [[INF] * W for _ in range(H)]
D[sh][sw] = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
que = deque([(sh, sw)])
while que:
	(nh, nw) = que.pop()
	for (dh, dw) in directions:
		for k in range(1, K + 1):
			(nx_h, nx_w) = (nh + k * dh, nw + k * dw)
			if not (0 <= nx_h < H and 0 <= nx_w < W):
				break
			if G[nx_h][nx_w] == '@':
				break
			if D[nx_h][nx_w] <= D[nh][nw]:
				break
			if D[nx_h][nx_w] > D[nh][nw] + 1:
				D[nx_h][nx_w] = D[nh][nw] + 1
				que.appendleft((nx_h, nx_w))
print(D[gh][gw] if D[gh][gw] != INF else -1)


import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
	(H, W, K) = map(int, readline().split())
	(x1, y1, x2, y2) = map(int, readline().split())
	(x1, y1, x2, y2) = (v - 1 for v in (x1, y1, x2, y2))
	C = [readline().rstrip() for i in range(H)]
	INF = 10 ** 10
	visited = [[INF] * W for i in range(H)]
	dist = [[0] * W for i in range(H)]
	dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	q = deque()
	q.append((x1, y1, 0))
	visited[x1][y1] = 0
	dist[x1][y1] = 0

	def aa(_i, _j, y, x, d):
		(i, j) = (_i, _j)
		for k in range(K):
			i += y
			j += x
			if not (0 <= i < H and 0 <= j < W):
				break
			if C[i][j] == '@':
				break
			if d > visited[i][j]:
				break
			if d == visited[i][j]:
				continue
			visited[i][j] = d
			dist[i][j] = d
			q.append((i, j, d))
	while q:
		(i, j, d) = q.popleft()
		for (y, x) in dirs:
			aa(i, j, y, x, d + 1)
	if visited[x2][y2] == INF:
		print(-1)
	else:
		print(dist[x2][y2])
solve()


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


import queue
INF = 10 ** 9
(H, W, K) = map(int, input().split())
(sx, sy, gx, gy) = map(int, input().split())
sentinels = [-1] * (W + 2)
MAP = [sentinels]
for _ in range(H):
	MAP.append([-1] + list(map(lambda c: INF if c == '.' else -1, input())) + [-1])
MAP.append(sentinels)
q = queue.Queue()
q.put((sx, sy))
MAP[sx][sy] = 0
while not q.empty():
	(x, y) = q.get()
	for d in range(1, K + 1):
		if MAP[x + d][y] > MAP[x][y] + 1:
			MAP[x + d][y] = MAP[x][y] + 1
			q.put((x + d, y))
		elif MAP[x + d][y] < MAP[x][y] + 1:
			break
	for d in range(1, K + 1):
		if MAP[x - d][y] > MAP[x][y] + 1:
			MAP[x - d][y] = MAP[x][y] + 1
			q.put((x - d, y))
		elif MAP[x - d][y] < MAP[x][y] + 1:
			break
	for d in range(1, K + 1):
		if MAP[x][y + d] > MAP[x][y] + 1:
			MAP[x][y + d] = MAP[x][y] + 1
			q.put((x, y + d))
		elif MAP[x][y + d] < MAP[x][y] + 1:
			break
	for d in range(1, K + 1):
		if MAP[x][y - d] > MAP[x][y] + 1:
			MAP[x][y - d] = MAP[x][y] + 1
			q.put((x, y - d))
		elif MAP[x][y - d] < MAP[x][y] + 1:
			break
if MAP[gx][gy] == INF:
	print(-1)
else:
	print(MAP[gx][gy])


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


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


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


def f_pond_skater():
	from heapq import heappush, heappop
	(H, W, K) = [int(i) for i in input().split()]
	(start_row, start_col, target_row, target_col) = [int(i) - 1 for i in input().split()]
	Grid = [input() for _ in range(H)]
	heap = []
	dist = [[float('inf')] * W for _ in range(H)]
	dist[start_row][start_col] = 0
	diff = ((0, 1), (1, 0), (0, -1), (-1, 0))
	heappush(heap, (0, start_row, start_col))
	while heap:
		(cost, row, col) = heappop(heap)
		cost_next = cost + 1
		if row == target_row and col == target_col:
			return cost
		for (dr, dc) in diff:
			(nr, nc) = (row, col)
			for _ in range(K):
				nr += dr
				nc += dc
				if not (0 <= nr < H and 0 <= nc < W) or Grid[nr][nc] == '@':
					break
				if dist[nr][nc] > cost_next:
					dist[nr][nc] = cost_next
					heappush(heap, (cost_next, nr, nc))
				elif dist[nr][nc] == cost_next:
					continue
				else:
					break
	return -1
print(f_pond_skater())


from collections import deque
from heapq import heappop, heappush
import numpy as np
from numba import njit

@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)')
def reachable(field, h2, w2, k):
	hw = h2 * w2
	up = np.full(hw, -1, dtype=np.int64)
	dw = np.full(hw, -1, dtype=np.int64)
	lf = np.full(hw, -1, dtype=np.int64)
	rg = np.full(hw, -1, dtype=np.int64)
	lf_tmp = -1
	for i in range(w2, hw - w2):
		if field[i]:
			if lf_tmp == -1:
				lf_tmp = i
			lf[i] = max(lf_tmp, i - k)
		else:
			lf_tmp = -1
	rg_tmp = -1
	for i in range(hw - w2, w2 - 1, -1):
		if field[i]:
			if rg_tmp == -1:
				rg_tmp = i
			rg[i] = min(rg_tmp, i + k)
		else:
			rg_tmp = -1
	wk = w2 * k
	for j in range(1, w2):
		up_tmp = -1
		for i in range(j, hw, w2):
			if field[i]:
				if up_tmp == -1:
					up_tmp = i
				up[i] = max(up_tmp, i - wk)
			else:
				up_tmp = -1
		dw_tmp = 0
		for i in range(hw - w2 + j, w2 - 1, -w2):
			if field[i]:
				if dw_tmp == -1:
					dw_tmp = i
				dw[i] = min(dw_tmp, i + wk)
			else:
				dw_tmp = -1
	return (up, dw, lf, rg)

@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)')
def solve(h2, w2, k, field, x1, y1, x2, y2):
	s = x1 * w2 + y1
	t = x2 * w2 + y2
	(up, dw, lf, rg) = reachable(field, h2, w2, k)
	INF = 10 ** 18
	ans = [[INF, INF] for _ in field]
	ans[s][0] = ans[s][1] = 0
	q = [(0, s)]
	while q:
		(cost, v) = heappop(q)
		if v == t:
			return cost
		nc = cost + 1
		for u in range(up[v], v, w2):
			if ans[u][0] <= nc:
				break
			ans[u][0] = nc
			heappush(q, (nc, u))
		for u in range(dw[v], v, -w2):
			if ans[u][0] <= nc:
				break
			ans[u][0] = nc
			heappush(q, (nc, u))
		for u in range(lf[v], v, 1):
			if ans[u][1] <= nc:
				break
			ans[u][1] = nc
			heappush(q, (nc, u))
		for u in range(rg[v], v, -1):
			if ans[u][1] <= nc:
				break
			ans[u][1] = nc
			heappush(q, (nc, u))
	return -1
(h, w, k) = list(map(int, input().split()))
(x1, y1, x2, y2) = list(map(int, input().split()))
h2 = h + 2
w2 = w + 2
field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
	field.append(0)
	field.extend(list(map('@.'.index, row)))
	field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))


from collections import deque
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
g = []
for i in range(h):
	g.append(input())
inf = 10 ** 9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1 - 1][y1 - 1] = 0
q = deque([(x1 - 1, y1 - 1)])
while q:
	(x, y) = q.popleft()
	if (x, y) == (x2 - 1, y2 - 1):
		break
	c = dp[x][y]
	for i in range(x + 1, min(x + k + 1, h)):
		if g[i][y] == '@':
			break
		if dp[i][y] == inf:
			q.append((i, y))
		if dp[i][y] >= c + 1:
			dp[i][y] = c + 1
		else:
			break
	for i in range(x - 1, max(x - k - 1, -1), -1):
		if g[i][y] == '@':
			break
		if dp[i][y] == inf:
			q.append((i, y))
		if dp[i][y] >= c + 1:
			dp[i][y] = c + 1
		else:
			break
	for j in range(y + 1, min(y + k + 1, w)):
		if g[x][j] == '@':
			break
		if dp[x][j] == inf:
			q.append((x, j))
		if dp[x][j] >= c + 1:
			dp[x][j] = c + 1
		else:
			break
	for j in range(y - 1, max(y - k - 1, -1), -1):
		if g[x][j] == '@':
			break
		if dp[x][j] == inf:
			q.append((x, j))
		if dp[x][j] >= c + 1:
			dp[x][j] = c + 1
		else:
			break
if dp[x2 - 1][y2 - 1] == inf:
	print(-1)
else:
	print(dp[x2 - 1][y2 - 1])


from collections import deque
(h, w, k) = map(int, input().split())
(y1, x1, gy, gx) = map(int, input().split())
m = ['@' * (w + 2)] + ['@' + input() + '@' for i in range(h)] + ['@' * (w + 2)]
opt = [(1, 0), (0, 1), (-1, 0), (0, -1)]
dq = deque([(y1, x1)])
ans = 0
temp = [[-1] * (w + 2) for i in range(h + 2)]
temp[y1][x1] = 0
cnt = 0
while dq:
	(y, x) = dq.popleft()
	for j in opt:
		y1 = y + j[0]
		x1 = x + j[1]
		if m[y1][x1] == '@':
			continue
		if temp[y1][x1] == -1 or temp[y1][x1] - temp[y][x] > 0:
			for i in range(k):
				if (temp[y1 + i * j[0]][x1 + i * j[1]] == -1 or temp[y1 + i * j[0]][x1 + i * j[1]] - temp[y][x] > 0) and m[y1 + i * j[0]][x1 + i * j[1]] == '.':
					if temp[y1 + i * j[0]][x1 + i * j[1]] - temp[y][x] == 1:
						continue
					temp[y1 + i * j[0]][x1 + i * j[1]] = temp[y][x] + 1
					dq.append((y1 + i * j[0], x1 + i * j[1]))
				else:
					break
print(temp[gy][gx])


import sys
from collections import deque

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return [LIST() for _ in range(n)]

def main():
	(H, W, K) = MAP()
	HH = max(H, W) + 2
	(x1, y1, x2, y2) = LIST()
	c = [[-1] + [0 if c == '.' else -1 for c in input()] + [-1] for i in range(H)]
	c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
	stack = deque([(x1, y1, 0), (x1, y1, 1), (x1, y1, 2), (x1, y1, 3)])
	(append, popleft) = (stack.append, stack.popleft)
	DX = (1, 0, -1, 0)
	DY = (0, 1, 0, -1)
	while stack:
		(x, y, d) = popleft()
		flag = True
		a = c[x][y] + 1
		for k in range(1, K + 1):
			(xx, yy) = (x + k * DX[d], y + k * DY[d])
			if c[xx][yy] == 0:
				b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
				if b == 0 or b == a + 1:
					append((xx, yy, (d - 1) % 4))
				b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
				if b == 0 or b == a + 1:
					append((xx, yy, (d + 1) % 4))
				c[xx][yy] = a
			elif c[xx][yy] != a:
				flag = False
				break
		if flag:
			append((xx, yy, d))
		if c[x2][y2] > 0:
			print(c[x2][y2])
			return
	print(-1)
	return
main()


from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
	queue = deque([[sy, sx]])
	visited[sy][sx] = 0
	while queue:
		(y, x) = queue.popleft()
		if [y, x] == [gy, gx]:
			return visited[y][x]
		for (j, k) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			l = 1
			while True:
				(new_y, new_x) = (y + j * l, x + k * l)
				if 0 <= new_y < H and 0 <= new_x < W:
					if maze[new_y][new_x] == '@':
						break
					elif visited[new_y][new_x] == -1:
						visited[new_y][new_x] = visited[y][x] + 1
						queue.append([new_y, new_x])
					elif visited[new_y][new_x] < visited[y][x] + 1:
						break
				else:
					break
				l += 1
				if l == K + 1:
					break
(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 = [0] * H
for i in range(H):
	C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
print(visited[x2][y2])


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


import sys
from collections import deque
(h, w, k) = map(int, sys.stdin.readline().rstrip('\n').split())
(sx, sy, gx, gy) = map(int, sys.stdin.readline().rstrip('\n').split())
(sx, sy, gx, gy) = (sx - 1, sy - 1, gx - 1, gy - 1)
labyrinth = [line.rstrip('\n') for line in sys.stdin]
INF = float('inf')
footprint = [[[(INF, INF)] * 4 for j in range(w)] for i in range(h)]
m = [(-1, 0), (0, 1), (1, 0), (0, -1)]
q = deque()
for d in range(4):
	footprint[sx][sy][d] = (1, 0)
	q.append((sx, sy, d, 1, 0))
while q:
	(x, y, d, c, kk) = q.popleft()
	for nd in range(4):
		if nd == d:
			(mx, my) = m[d]
			nkk = 1 if kk == k else kk + 1
			nc = c + 1 if kk == k else c
		else:
			(mx, my) = (0, 0)
			nkk = 0
			nc = c + 1
		nx = x + mx
		ny = y + my
		if 0 <= nx < h and 0 <= ny < w and (labyrinth[nx][ny] == '.') and (footprint[nx][ny][nd] > (nc, nkk)):
			footprint[nx][ny][nd] = (nc, nkk)
			if nc == c:
				q.appendleft((nx, ny, nd, nc, nkk))
			else:
				q.append((nx, ny, nd, nc, nkk))
ans = INF
for d in range(4):
	ans = min(ans, footprint[gx][gy][d][0])
ans = -1 if ans == INF else ans
print(ans)


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


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)


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1, 0, 1, 0)
Dx = (0, 1, 0, -1)
from collections import deque, defaultdict, Counter

def main():
	(H, W, K) = map(int, input().split())
	(sy, sx, gy, gx) = map(int, input().split())
	sy -= 1
	sx -= 1
	gy -= 1
	gx -= 1
	pond = [list(input()) for _ in range(H)]
	q = deque([(sy, sx)])
	dist = [[-1] * W for _ in range(H)]
	dist[sy][sx] = 0
	while q:
		(ny, nx) = q.popleft()
		for (dy, dx) in zip(Dy, Dx):
			(y, x) = (ny, nx)
			for _ in range(K):
				y += dy
				x += dx
				if y < 0 or y >= H:
					break
				if x < 0 or x >= W:
					break
				if pond[y][x] == '@':
					break
				if dist[y][x] >= 0 and dist[y][x] <= dist[ny][nx]:
					break
				if dist[y][x] < 0:
					dist[y][x] = dist[ny][nx] + 1
					q.append((y, x))
				if (y, x) == (gy, gx):
					break
	print(dist[gy][gx] if dist[gy][gx] >= 0 else -1)
main()


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


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


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
grid = [input() for _ in range(H)]

def inside(r, c):
	return 0 <= r < H and 0 <= c < W and (grid[r][c] != '@')
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = 10 ** 9
dist = [[INF] * W for _ in range(H)]
que = deque()
que.append([sx, sy])
dist[sx][sy] = 0
while que:
	[x, y] = que.popleft()
	for k in range(4):
		for d in range(1, K + 1):
			nx = x + d * dx[k]
			ny = y + d * dy[k]
			if not inside(nx, ny) or dist[nx][ny] <= dist[x][y]:
				break
			if dist[nx][ny] == INF:
				dist[nx][ny] = dist[x][y] + 1
				que.append([nx, ny])
if dist[gx][gy] == INF:
	print(-1)
else:
	print(dist[gx][gy])


from collections import deque
(h, w, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float('inf') for _ in range(w)] for _ in range(h)]
dq = deque([(b, a)])
depth[a][b] = 0
while dq:
	(x, y) = dq.popleft()
	if x == d and y == c:
		break
	for i in range(4):
		(nx, ny, K) = (x, y, k)
		while K:
			K -= 1
			nx += dx[i]
			ny += dy[i]
			if 0 <= nx <= w - 1 and 0 <= ny <= h - 1 and (maze[ny][nx] != '@') and (depth[ny][nx] > depth[y][x]):
				if depth[ny][nx] == depth[y][x] + 1:
					continue
				depth[ny][nx] = depth[y][x] + 1
				dq.append((nx, ny))
			else:
				break
print(depth[c][d] if depth[c][d] != float('inf') else -1)


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


from collections import deque
(h, w, k) = map(int, input().split())
(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())
cmap = [input() for _ in range(h)]
inf = float('inf')
seen = [[[(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):
	seen[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 (cmap[nx][ny] != '@') and (seen[nx][ny][nd] > (nc, nk)):
			seen[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, seen[x2][y2][d][0])
ans = -1 if ans == inf else ans
print(ans)


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)


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
(H, W, K) = map(int, input().split())
(x1, y1, x2, y2) = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]
(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m):
	return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0
q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q:
	(ccost, cpos) = heappop(q)
	if ccost > dist[cpos]:
		continue
	cx = cpos // 2 // W
	cy = cpos // 2 % W
	cmode = cpos % 2
	dir = [[(-1, 0), (1, 0)], [(0, -1), (0, 1)]]
	for (dx, dy) in dir[cmode]:
		(nx, ny) = (cx + dx, cy + dy)
		ncost = ccost + 1
		if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and (ncost < dist[pos(nx, ny, cmode)]):
			heappush(q, (ncost, pos(nx, ny, cmode)))
			dist[pos(nx, ny, cmode)] = ncost
	ncost = (ccost + K - 1) // K * K
	if ncost < dist[pos(cx, cy, cmode ^ 1)]:
		dist[pos(cx, cy, cmode ^ 1)] = ncost
		heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))
ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF:
	print(-1)
else:
	print((ans + K - 1) // K)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)

def main(input, print):
	vx = [0, 1, 0, -1]
	vy = [-1, 0, 1, 0]
	(H, W, K) = map(int, input().split())
	(x1, y1, x2, y2) = map(int, input().split())
	table = [[] for _ in range(H)]
	for i in range(H):
		table[i] = list(input().strip())
	q = deque()
	q.append((x1 - 1, y1 - 1, 0))
	table[x1 - 1][y1 - 1] = 0
	while len(q) > 0:
		(x, y, cnt) = q.popleft()
		for i in range(4):
			for k in range(1, K + 1):
				nx = x + vx[i] * k
				ny = y + vy[i] * k
				if nx < 0 or ny < 0 or nx >= H or (ny >= W):
					break
				if table[nx][ny] == '@':
					break
				if table[nx][ny] != '.':
					if table[nx][ny] < cnt + 1:
						break
					else:
						continue
				table[nx][ny] = cnt + 1
				q.append((nx, ny, cnt + 1))
	if table[x2 - 1][y2 - 1] == '.':
		print(-1)
	else:
		print(table[x2 - 1][y2 - 1])
main(sys.stdin.readline, print)


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)


(h, w, k) = map(int, input().split())
(sx, sy, gx, gy) = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
grid = ['' for _ in range(h)]
for i in range(h):
	grid[i] = input()
INF = 1001001001
costgrid = [[INF] * w for _ in range(h)]
import heapq
q = []
q.append((0, sx, sy))
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
ans = INF
while q:
	(cost, x, y) = heapq.heappop(q)
	for i in range(4):
		for j in range(1, k + 1):
			nx = x + dx[i] * j
			ny = y + dy[i] * j
			if not 0 <= nx < h:
				break
			if not 0 <= ny < w:
				break
			if grid[nx][ny] == '@':
				break
			if costgrid[nx][ny] <= cost:
				break
			if costgrid[nx][ny] > cost + 1:
				costgrid[nx][ny] = cost + 1
				heapq.heappush(q, (cost + 1, nx, ny))
				if nx == gx and ny == gy:
					ans = min(costgrid[nx][ny], ans)
					q = []
if ans != INF:
	print(ans)
else:
	print(-1)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
(H, W, K) = map(int, readline().split())
(x1, y1, x2, y2) = map(int, readline().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
C = read().split()
dist = [[-1] * W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
	(x, y) = d.popleft()
	if (x, y) == (x2, y2):
		print(dist[x][y])
		return
	for (dx, dy) in dxy:
		xx = x
		yy = y
		for i in range(K):
			xx += dx
			yy += dy
			if 0 <= xx < H and 0 <= yy < W and (C[xx][yy] != '@'):
				if 0 <= dist[xx][yy] <= dist[x][y]:
					break
				if dist[xx][yy] == -1:
					d.append([xx, yy])
				dist[xx][yy] = dist[x][y] + 1
			else:
				break
print(-1)


from collections import deque
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	inf = 10 ** 9
	(h, w, k) = MI()
	(x1, y1, x2, y2) = MI1()
	aa = [[0 if c == '@' else inf for c in SI()] for _ in range(h)]
	aa[x1][y1] = 0
	q = deque()
	q.append((x1, y1, 0))
	while q:
		(x, y, d) = q.popleft()
		for nx in range(x + 1, min(x + k + 1, h)):
			if aa[nx][y] == d + 1:
				continue
			if aa[nx][y] < d + 1:
				break
			aa[nx][y] = d + 1
			q.append((nx, y, d + 1))
		for nx in range(x - 1, max(x - k - 1, -1), -1):
			if aa[nx][y] == d + 1:
				continue
			if aa[nx][y] < d + 1:
				break
			aa[nx][y] = d + 1
			q.append((nx, y, d + 1))
		for ny in range(y + 1, min(y + k + 1, w)):
			if aa[x][ny] == d + 1:
				continue
			if aa[x][ny] < d + 1:
				break
			aa[x][ny] = d + 1
			q.append((x, ny, d + 1))
		for ny in range(y - 1, max(y - k - 1, -1), -1):
			if aa[x][ny] == d + 1:
				continue
			if aa[x][ny] < d + 1:
				break
			aa[x][ny] = d + 1
			q.append((x, ny, d + 1))
	ans = aa[x2][y2]
	if ans == inf:
		print(-1)
	else:
		print(ans)
main()


import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline

def RD():
	return sys.stdin.read()

def II():
	return int(input())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def TI():
	return tuple(map(int, input().split()))
from collections import deque

def main():
	(h, w, k) = MI()
	(x1, y1, x2, y2) = MI()
	G = ['@'] * (w + 2)
	for _ in range(h):
		G.append('@')
		G += list(map(str, input().rstrip()))
		G.append('@')
	G += ['@'] * (w + 2)
	G[x1 * (w + 2) + y1] = 0
	Q = deque()
	Q.append((x1 * (w + 2) + y1, 0))
	while Q:
		(now, d) = Q.popleft()
		for m in [1, -1, w + 2, -w - 2]:
			for i in range(1, k + 1):
				if G[now + m * i] == d or G[now + m * i] == '@':
					break
				elif G[now + m * i] == '.':
					G[now + m * i] = d + 1
					Q.append([now + m * i, d + 1])
				elif G[now + m * i] == d + 1:
					continue
				else:
					break
	if G[x2 * (w + 2) + y2] == '.':
		print(-1)
	else:
		print(G[x2 * (w + 2) + y2])
main()


from collections import deque
(H, W, K) = map(int, input().split())
(sx, sy, gx, gy) = (i - 1 for i in map(int, input().split()))
grid = []
inf = 1 << 30
reach = [[inf for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dif = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(H):
	grid.append(list(input()))
que = deque([(sx, sy)])
while que:
	(x, y) = que.popleft()
	for i in range(4):
		for k in range(1, K + 1):
			nx = x + k * dif[i][0]
			ny = y + k * dif[i][1]
			if nx < 0 or nx >= H or ny < 0 or (ny >= W) or (grid[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])
				que.append((nx, ny))
			if nx == gx and ny == gy:
				print(reach[nx][ny])
				exit()
print(-1)


from collections import deque

def main():
	(h, w, k) = map(int, input().split())
	(x, y, gx, gy) = map(int, input().split())
	x -= 1
	gx -= 1
	y -= 1
	gy -= 1
	c = [list(input()) for _ in range(h)]
	d = [[-1 for _ in range(w)] for _ in range(h)]
	dx = (1, 0, -1, 0)
	dy = (0, 1, 0, -1)
	que = deque()
	que.append((x, y))
	d[x][y] = 0
	while que:
		(qx, qy) = que.popleft()
		if qx == gx and qy == gy:
			break
		for i in range(4):
			for K in range(1, k + 1):
				nx = qx + dx[i] * K
				ny = qy + dy[i] * K
				if not (nx >= 0 and h > nx and (ny >= 0) and (w > ny)) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy] + 1):
					break
				if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy] + 1:
					d[nx][ny] = d[qx][qy] + 1
					que.append((nx, ny))
	print(d[gx][gy])
main()


Dy = [0, 1, 0, -1]
Dx = [1, 0, -1, 0]
(H, W, K) = map(int, input().split())
(y1, x1, y2, x2) = map(int, input().split())
C = ['@' + input() + '@' for _ in range(H)]
C = ['@' * (W + 2)] + C + ['@' * (W + 2)]
L = [[1] * (W + 2) for _ in range(H + 2)]
R = [[1] * (W + 2) for _ in range(H + 2)]
U = [[1] * (W + 2) for _ in range(H + 2)]
D = [[1] * (W + 2) for _ in range(H + 2)]
q = [(y1, x1)]
ans = 0
while q:
	q_new = []
	for (y0, x0) in q:
		if (y0, x0) == (y2, x2):
			print(ans)
			exit()
		for (dy, dx, Next) in zip(Dy, Dx, [L, R, U, D]):
			(y, x) = (y0, x0)
			sum_next = 0
			Path = [(y, x)]
			while True:
				sum_next += Next[y][x]
				y = y0 + dy * sum_next
				x = x0 + dx * sum_next
				if sum_next > K:
					break
				if C[y][x] == '@':
					break
				Path.append((y, x))
				q_new.append((y, x))
			for (path_y, path_x) in Path:
				Next[path_y][path_x] = abs(path_y - y) + abs(path_x - x)
	q = q_new
	ans += 1
print(-1)


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


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

def log(*args):
	print(*args, file=sys.stderr)

def main():
	(h, w, k) = map(int, input().strip().split())
	(x1, y1, x2, y2) = map(int, input().strip().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	m = []
	costs1 = [[None for j in range(w)] for i in range(h)]
	costs2 = [[None for j in range(w)] for i in range(h)]
	for _ in range(h):
		m.append(list(input().strip()))
	q1 = deque()
	q1.append((x1, y1, 0))
	costs1[x1][y1] = 0
	q2 = deque()
	q2.append((x2, y2, 0))
	costs2[x2][y2] = 0
	directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	while q1 and q2:
		(x, y, cost) = q1.popleft()
		if not costs2[x][y] is None:
			print(cost + costs2[x][y])
			return
		for (add_x, add_y) in directions:
			for dist in range(1, k + 1):
				new_x = x + add_x * dist
				new_y = y + add_y * dist
				if new_x >= h or new_x < 0 or new_y >= w or (new_y < 0) or (m[new_x][new_y] == '@') or (not costs1[new_x][new_y] is None and costs1[new_x][new_y] < cost + 1):
					break
				if costs1[new_x][new_y] is None:
					costs1[new_x][new_y] = cost + 1
					q1.append((new_x, new_y, cost + 1))
		(x, y, cost) = q2.popleft()
		if not costs1[x][y] is None:
			print(cost + costs1[x][y])
			return
		for (add_x, add_y) in directions:
			for dist in range(1, k + 1):
				new_x = x + add_x * dist
				new_y = y + add_y * dist
				if new_x >= h or new_x < 0 or new_y >= w or (new_y < 0) or (m[new_x][new_y] == '@') or (not costs2[new_x][new_y] is None and costs2[new_x][new_y] < cost + 1):
					break
				if costs2[new_x][new_y] is None:
					costs2[new_x][new_y] = cost + 1
					q2.append((new_x, new_y, cost + 1))
	print('-1')

def __starting_point():
	main()
__starting_point()


from collections import deque
printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
(h, w, k) = inm()
(x1, y1, x2, y2) = inm()
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c = []
for i in range(h):
	c.append(ins())
d = [[-1] * w for i in range(h)]
q = deque([(x1, y1)])
d[x1][y1] = 0
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while len(q) > 0:
	(x, y) = q.popleft()
	dd = d[x][y] + 1
	for (dx, dy) in dir:
		for i in range(1, k + 1):
			xx = x + i * dx
			yy = y + i * dy
			if xx < 0 or h <= xx or yy < 0 or (w <= yy) or (d[xx][yy] >= 0 and d[xx][yy] < dd) or (c[xx][yy] == '@'):
				break
			if d[xx][yy] == dd:
				continue
			d[xx][yy] = dd
			q.append((xx, yy))
			if xx == x2 and yy == y2:
				print(dd)
				exit()
print(-1)