#include <algorithm> #include <iostream> #include <cstring> #include <set> using namespace std; const int N = 6000000; const int ddi[] = { -1, 0, 1, 0 }; const int ddj[] = { 0, 1, 0, -1 }; char tt[N + 1], *aa[N]; set<int> jj, ii; int *dd[N], qu[N * 2], head, cnt; int n, m; void update(int i, int j, int d, int w) { if (dd[i][j] <= d) return; dd[i][j] = d; if (!w) qu[--head] = i * m + j, cnt++; else qu[head + cnt++] = i * m + j; jj.erase(i * m + j); ii.erase(j * n + i); } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int k; cin >> n >> m >> k; int is, js; cin >> is >> js, is--, js--; int it, jt; cin >> it >> jt, it--, jt--; for (int i = 0; i < n; i++) cin >> tt, aa[i] = strdup(tt); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { jj.insert(i * m + j); ii.insert(j * n + i); } for (int i = 0; i < n; i++) { dd[i] = new int[m]; for (int j = 0; j < m; j++) dd[i][j] = n * m; } head = n * m; update(is, js, 0, 0); int ans = n * m; while (cnt--) { int ij = qu[head++], i = ij / m, j = ij % m, d = dd[i][j]; if (i - k <= it && it <= i + k && j - k <= jt && jt <= j + k && abs(it - i) + abs(jt - j) != k * 2) ans = min(ans, d + 1); for (int h = 0; h < 4; h++) { int i_ = i + ddi[h], j_ = j + ddj[h]; if (0 <= i_ && i_ < n && 0 <= j_ && j_ < m && aa[i_][j_] == '.') { if (i_ == it && j_ == jt) ans = min(ans, d); update(i_, j_, d, 0); } if (h % 2 == 0) { int jl = max(j - k + 1, 0), jr = min(j + k - 1, m - 1); i_ = i + ddi[h] * k; if (0 <= i_ && i_ < n) while (true) { auto it = jj.lower_bound(i_ * m + jl); if (it == jj.end()) break; int ij = *it; if (ij > i_ * m + jr) break; update(i_, ij - i_ * m, d + 1, 1); } } else { int il = max(i - k + 1, 0), ir = min(i + k - 1, n - 1); j_ = j + ddj[h] * k; if (0 <= j_ && j_ < m) while (true) { auto it = ii.lower_bound(j_ * n + il); if (it == ii.end()) break; int ji = *it; if (ji > j_ * n + ir) break; update(ji - j_ * n, j_, d + 1, 1); } } } } cout << ans << '\n'; return 0; }