#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int R, C, N;
vector<string> grid;
vector<int> dist_arr;
// Одномерные DSU для быстрого пропуска уже пройденных ячеек
vector<int> p_col;
vector<int> p_row_inner;
vector<int> p_row_outer;
inline int find_col(int r, int c) {
int idx = r * (C + 1) + c;
if (p_col[idx] == c) return c;
return p_col[idx] = find_col(r, p_col[idx]);
}
inline void remove_col(int r, int c) {
int idx = r * (C + 1) + c;
p_col[idx] = find_col(r, c + 1);
}
inline int find_row_inner(int r, int c) {
int idx = r * C + c;
if (p_row_inner[idx] == r) return r;
return p_row_inner[idx] = find_row_inner(p_row_inner[idx], c);
}
inline int find_row_outer(int r, int c) {
int idx = r * C + c;
if (p_row_outer[idx] == r) return r;
return p_row_outer[idx] = find_row_outer(p_row_outer[idx], c);
}
inline void remove_row_outer(int r, int c) {
int idx = r * C + c;
p_row_outer[idx] = find_row_outer(r + 1, c);
}
inline void remove_row_inner(int r, int c) {
int idx = r * C + c;
p_row_inner[idx] = find_row_inner(r + 1, c);
remove_row_outer(r, c); // Inner-покрытие перекрывает outer, удаляем и оттуда
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> R >> C >> N)) return 0;
int sr, sc, gr, gc;
cin >> sr >> sc >> gr >> gc;
sr--; sc--; gr--; gc--;
grid.resize(R);
for(int i = 0; i < R; ++i) {
cin >> grid[i];
}
if (sr == gr && sc == gc) {
cout << 0 << "\n";
return 0;
}
dist_arr.assign(R * C, -1);
p_col.resize(R * (C + 1));
for(int r = 0; r < R; ++r) {
for(int c = 0; c <= C; ++c) {
p_col[r * (C + 1) + c] = c;
}
}
p_row_inner.resize((R + 1) * C);
p_row_outer.resize((R + 1) * C);
for(int r = 0; r <= R; ++r) {
for(int c = 0; c < C; ++c) {
p_row_inner[r * C + c] = r;
p_row_outer[r * C + c] = r;
}
}
vector<pair<int, int>> Q_current;
dist_arr[sr * C + sc] = 0;
remove_col(sr, sc);
Q_current.push_back({sr, sc});
int level = 0;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!Q_current.empty()) {
queue<pair<int, int>> q0;
for (auto p : Q_current) q0.push(p);
vector<pair<int, int>> S_L;
// 1. Сначала исследуем все клетки с нулевой стоимостью (по белым клеткам)
while (!q0.empty()) {
auto [r, c] = q0.front();
q0.pop();
S_L.push_back({r, c});
if (r == gr && c == gc) {
cout << level << "\n";
return 0;
}
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
if (grid[nr][nc] == '.') {
if (dist_arr[nr * C + nc] == -1) {
dist_arr[nr * C + nc] = level;
remove_col(nr, nc);
q0.push({nr, nc});
}
}
}
}
}
vector<pair<int, int>> Q1_inner, Q1_outer;
// 2. Расширение по вертикали (имитация 1D прыжка для штампа)
for (auto [r, c] : S_L) {
// Внутренняя (широкая) вертикаль
int min_r_in = max(0, r - N + 1);
int max_r_in = min(R - 1, r + N - 1);
int curr_r = find_row_inner(min_r_in, c);
while (curr_r <= max_r_in) {
Q1_inner.push_back({curr_r, c});
remove_row_inner(curr_r, c);
curr_r = find_row_inner(curr_r, c);
}
// Крайняя верхняя и нижняя граница действия штампа
int r_out1 = r - N;
if (r_out1 >= 0 && find_row_outer(r_out1, c) == r_out1) {
Q1_outer.push_back({r_out1, c});
remove_row_outer(r_out1, c);
}
int r_out2 = r + N;
if (r_out2 < R && find_row_outer(r_out2, c) == r_out2) {
Q1_outer.push_back({r_out2, c});
remove_row_outer(r_out2, c);
}
}
vector<pair<int, int>> Q_next;
// 3. Расширение по горизонтали
for (auto [r, c] : Q1_inner) {
int min_c = max(0, c - N);
int max_c = min(C - 1, c + N);
int curr_c = find_col(r, min_c);
while (curr_c <= max_c) {
dist_arr[r * C + curr_c] = level + 1;
remove_col(r, curr_c);
Q_next.push_back({r, curr_c});
curr_c = find_col(r, curr_c);
}
}
for (auto [r, c] : Q1_outer) {
int min_c = max(0, c - N + 1);
int max_c = min(C - 1, c + N - 1);
int curr_c = find_col(r, min_c);
while (curr_c <= max_c) {
dist_arr[r * C + curr_c] = level + 1;
remove_col(r, curr_c);
Q_next.push_back({r, curr_c});
curr_c = find_col(r, curr_c);
}
}
// Переходим на следующую "волну" штамповки
Q_current = move(Q_next);
level++;
}
return 0;
}
