#pragma target("arch=icelake-server")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>
using namespace std;
typedef long long ll;
typedef long double ld;
int log_ = 12;
int inf = 1000000007;
long long mod = 998244353;
int p = 499;
int NADIYA = 39;
vector <pair <int, int>> go = { {0 , 1} , {0 , -1} , {1 , 0} , {-1 , 0} };
vector <vector <int>> deep;
vector <vector <bool>> t;
struct DSU
{
int n, m;
vector <int> link;
vector <int> w;
vector <int> answer;
int T = 0;
int find(int ind)
{
if (link[ind] == ind)
return ind;
link[ind] = find(link[ind]);
return link[ind];
}
pair <int , int> lower_bound(int i, int j)
{
int i_ = i * m + j;
int ans = answer[find(i_)];
return { ans / m , ans % m };
}
void erase(int i, int j)
{
int i_ = i;
int j_ = j;
if (T == 0)
{
i_++;
}
else
{
j_++;
}
int i1 = i * m + j;
int i2 = i_ * m + j_;
i1 = find(i1);
i2 = find(i2);
int r = answer[i2];
if (w[i1] < w[i2])
swap(i1, i2);
link[i2] = i1;
w[i1] += w[i2];
answer[i1] = r;
}
void init(int N , int M , int t)
{
T = t;
n = N + 1;
m = M+1;
link.resize(n * m);
answer.resize(n * m);
w.resize(n * m, 1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
link[i * m + j] = i * m + j;
answer[i * m + j] = i * m + j;
}
}
link.resize(n * m);
}
};
int n, m;
bool checer(int i, int j) {
if ((i < 0) or (j < 0))
return false;
if ((i >= n) or (j >= m))
return false;
return true;
}
queue<pair <int, int>> q1;
queue<pair <int, int>> q2;
DSU vs_n;
DSU vs_m;
void dfs(int i, int j) {
vs_n.erase(i , j);
vs_m.erase(i , j);
for (int k = 0; k < 4; k++) {
int i_ = i + go[k].first;
int j_ = j + go[k].second;
if (checer(i_, j_) == true) {
if ((deep[i_][j_] == inf) and (t[i_][j_] == 0)) {
deep[i_][j_] = deep[i][j];
q1.push({ i_, j_ });
dfs(i_, j_);
continue;
}
}
}
}
vector <vector <int>> t2;
int k;
void dfs2(int i, int j , int x) {
t2[i][j]++;
for (int K = 0; K < 4; K++) {
int i_ = i + go[K].first;
int j_ = j + go[K].second;
if (checer(i_, j_) == true) {
if (((deep[i_][j_] == x) and (t2[i_][j_] == 0)) or ((deep[i_][j_] == x - 1) and (t2[i_][j_] == 1))) {
if (abs(j_ - j) == 1) {
int P = (j_ - j) * k;
int j__ = j_ + P;
if ((j__ < m) and (j__ >= 0))
{
int mn_ = i_ - k + 1;
int mx_ = i_ + k - 1;
mn_ = max(mn_, 0);
mx_ = min(mx_, n - 1);
while (vs_m.lower_bound( mn_ , j__).first <= mx_) {
int i__ = vs_m.lower_bound(mn_, j__).first;
deep[i__][j__] = deep[i_][j_] + 1;
q2.push({ i__, j__ });
vs_m.erase(i__, j__);
//vs_m[j__].erase(i__);
vs_n.erase(i__, j__);
//vs_n[i__].erase(j__);
}
}
P /= k;
P *= k - 1;
int i2 = i_ - k;
int j2 = j_ + P;
if ((checer(i2, j2) == true) and (vs_n.lower_bound(i2 , j2 ) == make_pair(i2 , j2))) {
vs_m.erase(i2, j2);
vs_n.erase(i2, j2);
//vs_n[i2].erase(j2);
//vs_m[j2].erase(i2);
deep[i2][j2] = deep[i_][j_] + 1;
q2.push({ i2 , j2 });
}
i2 = i_ + k;
j2 = j_ + P;
if ((checer(i2, j2) == true) and (vs_n.lower_bound(i2, j2) == make_pair(i2, j2))) {
vs_m.erase(i2, j2);
vs_n.erase(i2, j2);
//vs_n[i2].erase(j2);
//vs_m[j2].erase(i2);
deep[i2][j2] = deep[i_][j_] + 1;
q2.push({ i2 , j2 });
}
}
if (abs(i_ - i) == 1) {
int P = (i_ - i) * k;
int i__ = i_ + P;
if ((i__ < n) and (i__ >= 0))
{
int mn_ = j_ - k + 1;
int mx_ = j_ + k - 1;
mn_ = max(mn_, 0);
mx_ = min(mx_, m - 1);
while (vs_n.lower_bound(i__ , mn_).second <= mx_) {
int j__ = vs_n.lower_bound(i__, mn_).second;
deep[i__][j__] = deep[i_][j_] + 1;
q2.push({ i__, j__ });
vs_m.erase(i__, j__);
//vs_m[j__].erase(i__);
vs_n.erase(i__, j__);
//vs_n[i__].erase(j__);
}
}
P /= k;
P *= k - 1;
int j2 = j_ - k;
int i2 = i_ + P;
if ((checer(i2, j2) == true) and (vs_n.lower_bound(i2, j2) == make_pair(i2, j2))) {
vs_m.erase(i2, j2);
vs_n.erase(i2, j2);
deep[i2][j2] = deep[i_][j_] + 1;
q2.push({ i2 , j2 });
}
j2 = j_ + k;
i2 = i_ + P;
if ((checer(i2, j2) == true) and (vs_n.lower_bound(i2, j2) == make_pair(i2, j2))) {
vs_m.erase(i2, j2);
vs_n.erase(i2, j2);
deep[i2][j2] = deep[i_][j_] + 1;
q2.push({ i2 , j2 });
}
}
dfs2(i_, j_ , x);
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> k;
int i_st, j_st;
cin >> i_st >> j_st;
i_st--;
j_st--;
int i_fi, j_fi;
cin >> i_fi >> j_fi;
i_fi--;
j_fi--;
t.resize(n);
for (int i = 0; i < n; i++) {
t[i].resize(m);
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '.')
t[i][j] = 0;
else
t[i][j] = 1;
}
}
vs_n.init(n, m , 1);
vs_m.init(n, m , 0);
deep.resize(n);
for (int i = 0; i < n; i++) {
deep[i].resize(m, inf);
}
deep[i_st][j_st] = 0;
vs_n.erase(i_st , j_st);
vs_m.erase(i_st, j_st);
q1.push({ i_st , j_st });
t2.resize(n);
for (int i = 0; i < n; i++)
{
t2[i].resize(m);
}
for (int d = 0; d < n * m; d++) {
int d__ = inf;
int i_ = -1;
int j_ = -1;
while (q1.size() > 0) {
int i = q1.front().first;
int j = q1.front().second;
q1.pop();
if (d__ > abs(i - i_fi) + abs(j - j_fi)) {
d__ = abs(i - i_fi) + abs(j - j_fi);
i_ = i;
j_ = j;
}
dfs(i, j);
}
if (i_ != -1)
{
for (int pl = -k; pl <= k; pl++) {
int i__ = i_ + pl;
int mn_ = j_ - k;
int mx_ = j_ + k;
if (abs(pl) == k) {
mn_++;
mx_--;
}
mn_ = max(mn_, 0);
mx_ = min(mx_, m - 1);
if ((i__ < 0) or (i__ >= n))
continue;
while (vs_n.lower_bound(i__ , mn_).second <= mx_) {
int j__ = vs_n.lower_bound(i__, mn_).second;
vs_n.erase(i__, j__);
vs_m.erase(i__, j__);
deep[i__][j__] = deep[i_][j_] + 1;
q2.push({ i__ , j__ });
}
}
dfs2(i_, j_ , d);
}
swap(q1, q2);
}
int ans = inf;
for (int K = 0; K < 4; K++)
{
int i = i_fi + go[K].first;
int j = j_fi + go[K].second;
if (checer(i, j))
{
ans = min(ans, deep[i][j]);
}
}
cout << min(ans ,deep[i_fi][j_fi]);
}
/*
6 6 1
1 6
2 3
..#.#.
##.###
####.#
...###
##.##.
.#.##.
*/
