#include <bits/stdc++.h>
using namespace std;
pair<int, int> operator + (const pair<int, int>& a, const pair<int, int>& b) {
return {a.first + b.first, a.second + b.second};
}
int nbLigs, nbCols, cote;
int lDeb, cDeb, lFin, cFin;
vector<string> terrain;
bool estDans(pair<int, int> p) {
return p.first >= 0 && p.second >= 0
&& p.first < nbLigs && p.second < nbCols;
}
vector<pair<int, int>> aExplorer;
vector<vector<bool>> explorees, dansAExplorer;
pair<int, int> deps[4] = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
};
vector<pair<int, int>> expand(vector<pair<int, int>> cells,
pair<int, int> dir) {
vector<pair<int, int>> nouvCells;
for(pair<int, int> cell : cells) {
pair<int, int> nxt = cell + dir;
if(estDans(nxt)
&& !dansAExplorer[nxt.first][nxt.second]) {
aExplorer.push_back(nxt);
terrain[nxt.first][nxt.second] = '.';
dansAExplorer[nxt.first][nxt.second] = true;
nouvCells.push_back(nxt);
}
}
return nouvCells;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> nbLigs >> nbCols >> cote;
cin >> lDeb >> cDeb >> lFin >> cFin;
lDeb--; cDeb--; lFin--; cFin--;
for(int iLig = 0;iLig < nbLigs;iLig++) {
string lig;
cin >> lig;
terrain.push_back(lig);
}
explorees = vector<vector<bool>>(
nbLigs, vector<bool>(nbCols, false)
);
dansAExplorer = vector<vector<bool>>(
nbLigs, vector<bool>(nbCols, false)
);
dansAExplorer[lDeb][cDeb] = true;
aExplorer.push_back({lDeb, cDeb});
int dist = 0;
while(true) {
vector<pair<int, int>> murs;
while(!aExplorer.empty()) {
pair<int, int> cell = aExplorer.back();
aExplorer.pop_back();
if(terrain[cell.first][cell.second] == '#') {
murs.push_back({cell.first, cell.second});
}
else {
explorees[cell.first][cell.second] = true;
for(pair<int, int> dep : deps) {
pair<int, int> nxt = cell + dep;
if(estDans(nxt) && !dansAExplorer[nxt.first][nxt.second]) {
dansAExplorer[nxt.first][nxt.second] = true;
aExplorer.push_back(nxt);
}
}
}
}
if(explorees[lFin][cFin]) {
break;
}
dist++;
for(pair<int, int> cell : murs) {
aExplorer.push_back(cell);
terrain[cell.first][cell.second] = '.';
dansAExplorer[cell.first][cell.second] = true;
}
vector<pair<int, int>> cellsH[2] = {murs, murs};
vector<pair<int, int>> vues = murs;
for(int iFois = 0;iFois < cote - 1;iFois++) {
cellsH[0] = expand(cellsH[0], deps[0]);
vues.insert(vues.end(), cellsH[0].begin(), cellsH[0].end());
cellsH[1] = expand(cellsH[1], deps[2]);
vues.insert(vues.end(), cellsH[1].begin(), cellsH[1].end());
}
vector<pair<int, int>> cellsV[2] = {vues, vues};
for(int iFois = 0;iFois < cote - 1;iFois++) {
cellsV[0] = expand(cellsV[0], deps[1]);
cellsV[1] = expand(cellsV[1], deps[3]);
}
}
cout << dist << endl;
return 0;
}
