#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
const int INF = 1e9, MOD = 1e9 + 7;
void solve();
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int q = 1;
while (q--) {
solve();
}
}
pair<int, int> cord[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void solve() {
int r, c, n;
cin >> r >> c >> n;
int sr, sc, gr, gc;
cin >> sr >> sc >> gr >> gc;
sr--, sc--, gr--, gc--;
vector<char> a(r * c);
for (int i = 0; i < r * c; i++) {
cin >> a[i];
}
if (r > c) {
swap(r, c);
swap(sr, sc);
swap(gr, gc);
vector<char> nw(r * c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
nw[i * c + j] = a[j * r + i];
}
}
a = std::move(nw);
}
if (n >= r) {
int head = 0;
vector<pair<int, int>> bfs;
bfs.reserve(r * c);
bfs.emplace_back(sr, sc);
vector<int> used(r * c, 0);
used[sr * c + sc] = 1;
int mn = sc, mx = sc;
while (head < (int)bfs.size()) {
auto [i, j] = bfs[head++];
mn = min(mn, j); mx = max(mx, j);
for (auto [fx, fy] : cord) {
int x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x * c + y] == '#') {
continue;
}
if (used[x * c + y]) {
continue;
}
used[x * c + y] = 1;
bfs.emplace_back(x, y);
}
}
int col = 0;
int lf = sc + 1, rf = sc - 1;
while (!used[gr * c + gc]) {
int nwl = max(0, mn - n), nwr = min(c - 1, mx + n);
for (int i = 0; i < r; i++) {
int row_off = i * c;
for (int j = nwl; j < lf; j++) used[row_off + j] = 1;
for (int j = rf + 1; j <= nwr; j++) used[row_off + j] = 1;
}
col++;
lf = nwl, rf = nwr;
for (int i = 0; i < r; i++) {
bfs.emplace_back(i, lf);
bfs.emplace_back(i, rf);
}
while (head < (int)bfs.size()) {
auto [i, j] = bfs[head++];
mn = min(mn, j); mx = max(mx, j);
for (auto [fx, fy] : cord) {
int x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x * c + y] == '#') {
continue;
}
if (used[x * c + y]) {
continue;
}
used[x * c + y] = 1;
bfs.emplace_back(x, y);
}
}
}
cout << col << "\n";
return;
}
vector<int> used(r * c, 0);
vector<int> nxt(r * (c + 1));
for (int i = 0; i < r; i++) {
int offset = i * (c + 1);
for (int j = 0; j <= c; j++) {
nxt[offset + j] = j;
}
}
auto get_nxt = [&](int i, int j) -> int {
int offset = i * (c + 1);
int root = j;
while (root != nxt[offset + root]) root = nxt[offset + root];
int curr = j;
while (curr != root) {
int nxt_curr = nxt[offset + curr];
nxt[offset + curr] = root;
curr = nxt_curr;
}
return root;
};
int col = 0;
int head = 0;
vector<pair<int, int>> bfs;
bfs.reserve(r * c);
bfs.emplace_back(sr, sc);
used[sr * c + sc] = 1;
nxt[sr * (c + 1) + sc] = sc + 1;
vector<pair<int, int>> elems;
elems.reserve(r * c);
while (head < (int)bfs.size()) {
auto [i, j] = bfs[head++];
elems.emplace_back(i, j);
for (auto [fx, fy] : cord) {
int x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x * c + y] == '#') {
continue;
}
if (used[x * c + y]) {
continue;
}
used[x * c + y] = 1;
nxt[x * (c + 1) + y] = y + 1;
bfs.emplace_back(x, y);
}
}
while (!used[gr * c + gc]) {
col++;
for (auto [x, y] : elems) {
if (used[gr * c + gc]) {
cout << col << "\n";
return;
}
int max_i = min(r - 1, x + n);
for (int i = max(0, x - n); i <= max_i; i++) {
if (used[gr * c + gc]) {
cout << col << "\n";
return;
}
int lf = max(0, y - n), rf = min(c - 1, y + n);
if (abs(x - i) == n) {
lf = max(0, y - n + 1), rf = min(c - 1, y + n - 1);
}
int cur = get_nxt(i, lf);
int offset = i * (c + 1);
while (cur <= rf) {
if (used[gr * c + gc]) {
cout << col << "\n";
return;
}
used[i * c + cur] = 1;
bfs.emplace_back(i, cur);
nxt[offset + cur] = cur + 1;
cur = get_nxt(i, cur);
}
}
}
vector<pair<int, int>> nw;
nw.reserve(bfs.size() - head);
while (head < (int)bfs.size()) {
if (used[gr * c + gc]) {
cout << col << "\n";
return;
}
auto [i, j] = bfs[head++];
nw.emplace_back(i, j);
for (auto [fx, fy] : cord) {
int x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x * c + y] == '#') {
continue;
}
if (used[x * c + y]) {
continue;
}
used[x * c + y] = 1;
nxt[x * (c + 1) + y] = y + 1;
bfs.emplace_back(x, y);
}
}
elems = std::move(nw);
}
cout << col << "\n";
}
