#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C, N;
cin >> R >> C >> N;
int Sr, Sc, Gr, Gc;
cin >> Sr >> Sc >> Gr >> Gc;
Sr--; Sc--; Gr--; Gc--; // Convert to 0-indexed
vector<string> grid(R);
for (int i = 0; i < R; i++) {
cin >> grid[i];
}
// Check if goal is reachable
auto canReach = [&](const vector<string>& g) -> bool {
vector<vector<bool>> visited(R, vector<bool>(C, false));
queue<pair<int, int>> q;
q.push({Sr, Sc});
visited[Sr][Sc] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (x == Gr && y == Gc) return true;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < R && ny >= 0 && ny < C &&
!visited[nx][ny] && g[nx][ny] == '.') {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
};
if (canReach(grid)) {
cout << 0 << endl;
return 0;
}
// Generate all possible stamp positions
vector<pair<int, int>> stamps;
for (int a = 0; a <= R - N; a++) {
for (int b = 0; b <= C - N; b++) {
stamps.push_back({a, b});
}
}
int numStamps = stamps.size();
// BFS on stamp combinations
for (int ops = 1; ops <= min(20, numStamps); ops++) {
// Try all combinations of ops stamps using recursion with early termination
function<bool(int, int, vector<string>&)> solve = [&](int pos, int used, vector<string>& g) -> bool {
if (used == ops) {
return canReach(g);
}
if (pos >= numStamps || used + (numStamps - pos) < ops) {
return false;
}
// Early termination: if already reachable, no need to try more stamps
if (canReach(g)) return true;
// Try not using this stamp
if (solve(pos + 1, used, g)) return true;
// Try using this stamp
vector<string> newGrid = g;
int a = stamps[pos].first;
int b = stamps[pos].second;
for (int i = a; i < a + N; i++) {
for (int j = b; j < b + N; j++) {
newGrid[i][j] = '.';
}
}
if (solve(pos + 1, used + 1, newGrid)) return true;
return false;
};
vector<string> currentGrid = grid;
if (solve(0, 0, currentGrid)) {
cout << ops << endl;
return 0;
}
}
return 0;
}
