#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using namespace std;
struct cell {
int dir, l, c;
};
struct distancee {
int dist, dir, distL, distC;
};
bool operator < ( distancee a, distancee b ) {
if ( a.dist == b.dist ) {
int valA = (a.dir < 2 ? max( a.distL, a.distC ) : min( a.distL, a.distC ));
int valB = (b.dir < 2 ? max( b.distL, b.distC ) : min( b.distL, b.distC ));
return valA < valB;
}
return a.dist < b.dist;
}
struct elempq {
cell c;
distancee d;
bool operator < ( const elempq &x ) const {
return x.d < d;
}
};
const int MAX_N = 2500;
const int INF = 1e7;
int dl[4] = { 1, 0, -1, 0 }, dc[4] = { 0, 1, 0, -1 };
vector<distancee> minDist[5][MAX_N];
vector<bool> isBlocked[MAX_N], vis[5][MAX_N];
queue<elempq> pq;
int main() {
int n, m, k, sl, sc, gl, gc;
scanf( "%d%d%d", &n, &m, &k );
scanf( "%d%d", &sl, &sc );
scanf( "%d%d", &gl, &gc );
for ( int l = 0; l <= n + 1; l++ ) {
isBlocked[l].resize( m + 2 );
for ( int d = 0; d < 5; d++ ) {
minDist[d][l].resize( m + 2 );
for ( int c = 0; c <= m + 1; c++ )
minDist[d][l][c] = { INF, d, 0, 0 };
vis[d][l].resize( m + 2 );
}
}
for ( int l = 1; l <= n; l++ ) {
char ch;
scanf( "%c", &ch );
for ( int c = 1; c <= m; c++ ) {
scanf( "%c", &ch );
isBlocked[l][c] = (ch == '#');
}
}
for ( int l = 0; l <= n + 1; l++ ) {
isBlocked[l][0] = isBlocked[l][m + 1] = true;
for ( int d = 0; d < 5; d++ )
minDist[d][l][0] = minDist[d][l][m + 1] = { -INF, d, 0, 0 };
}
for ( int c = 0; c <= m + 1; c++ ) {
isBlocked[0][c] = isBlocked[n + 1][c] = true;
for ( int d = 0; d < 5; d++ )
minDist[d][0][c] = minDist[d][n + 1][c] = { -INF, d, 0, 0 };
}
minDist[4][sl][sc] = { 0, 4, 0, 0 };
pq.push( { 4, sl, sc, minDist[4][sl][sc] } );
while ( !pq.empty() ) {
cell a = pq.front().c;
distancee dd = pq.front().d;
pq.pop();
int dir = a.dir, l = a.l, c = a.c;
//printf( "celula %d %d %d cu distanta %d %d %d %d\n", dir, l, c, minDist[dir][l][c].dir, minDist[dir][l][c].dist, minDist[dir][l][c].distL, minDist[dir][l][c].distC );
if ( minDist[dir][l][c] < dd )
continue;
if ( dir == 4 ) {
for ( int d = 0; d < 4; d++ ) {
int newL = l + dl[d], newC = c + dc[d];
distancee newDist = minDist[dir][l][c];
if ( isBlocked[newL][newC] ) {
newDist.dir = 0;
newDist.distL = newDist.distC = 1;
}
if ( newDist < minDist[newDist.dir][newL][newC] ) {
minDist[newDist.dir][newL][newC] = newDist;
pq.push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
}
}
} else {
for ( int d = 0; d < 4; d++ ) {
int newL = l + dl[d], newC = c + dc[d];
distancee newDist = minDist[dir][l][c];
if ( !isBlocked[newL][newC] ) {
newDist.dir = 4;
newDist.dist++;
newDist.distL = newDist.distC = 0;
if ( newDist < minDist[newDist.dir][newL][newC] ) {
minDist[newDist.dir][newL][newC] = newDist;
pq.push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
}
}
newDist = minDist[dir][l][c];
if ( newDist.distL == k ) {
if ( newDist.distC == k ) {
newDist.dist++;
newDist.dir = 0;
newDist.distL = newDist.distC = 1;
} else {
if ( d % 2 == 0 )
continue;
if ( newDist.distC == 1 )
newDist.dir += 2;
newDist.distC++;
}
} else if ( newDist.distC == k ) {
if ( d % 2 == 1 )
continue;
if ( newDist.distL == 1 )
newDist.dir += 2;
newDist.distL++;
} else if ( newDist.distL == 1 ) {
if ( newDist.distC == 1 ) {
if ( d % 2 == 0 ) {
newDist.distL++;
newDist.dir = 0;
} else {
newDist.distC++;
newDist.dir = 1;
}
} else {
if ( d % 2 == 0 )
continue;
newDist.distC++;
}
} else if ( newDist.distC == 1 ) {
if ( d % 2 == 1 )
continue;
newDist.distL++;
}
if ( newDist < minDist[newDist.dir][newL][newC] ) {
minDist[newDist.dir][newL][newC] = newDist;
pq.push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
}
}
}
}
int ans = minDist[4][gl][gc].dist;
for ( int l = 1; l <= n; l++ ) {
for ( int c = 1; c <= m; c++ ) {
if ( !isBlocked[l][c] && abs( l - gl ) <= k - 1 && abs( c - gc ) <= k - 1 )
ans = min( ans, minDist[4][l][c].dist + 1 );
}
}
cout << ans << "\n";
return 0;
}
