#include <algorithm> #include <iostream> #include <cstring> 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 + 1]; int dd[N * 5], qu[N * 6], head, cnt; int n, m, k; int encode(int i, int j, int z) { return (i * m + j) * 5 + z; } void upd(int i, int j, int z, int d, int w) { int ijz = encode(i, j, z); if (dd[ijz] <= (d += w)) return; dd[ijz] = d; if (!w) qu[--head] = ijz, cnt++; else qu[head + cnt++] = ijz; } void updsq(int il, int ir, int jl, int jr, int d) { if (ir < 0 || n <= il || jr < 0 || m <= jl) return; il = max(il, 0); ir = min(ir, n - 1); jl = max(jl, 0); jr = min(jr, m - 1); int il_ = min((il + k - 1) / k * k, n - 1); int ir_ = ir / k * k; int jl_ = min((jl + k - 1) / k * k, m - 1); int jr_ = jr / k * k; if (il_ <= ir && jl_ <= jr) upd(il, jl, 1, d, 1); if (il_ <= ir && jr_ >= jl) upd(il, jr, 2, d, 1); if (ir_ >= il && jl_ <= jr) upd(ir, jl, 3, d, 1); if (ir_ >= il && jr_ >= jl) upd(ir, jr, 4, d, 1); } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); 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, strcpy(aa + i * m, tt); for (int ijz = 0; ijz < n * m * 5; ijz++) dd[ijz] = n * m; head = n * m, upd(is, js, 0, 0, 0); while (cnt--) { int ijz = qu[head++], i = ijz / 5 / m, j = ijz / 5 % m, z = ijz % 5, d = dd[ijz]; if (z == 0) { 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_ * m + j_] == '.') upd(i_, j_, z, d, 0); } updsq(i - k, i - 1, j - k + 1, j, d); updsq(i - k, i - 1, j, j + k - 1, d); updsq(i + 1, i + k, j - k + 1, j, d); updsq(i + 1, i + k, j, j + k - 1, d); updsq(i - k + 1, i, j - k, j - 1, d); updsq(i, i + k - 1, j - k, j - 1, d); updsq(i - k + 1, i, j + 1, j + k, d); updsq(i, i + k - 1, j + 1, j + k, d); } else { upd(i, j, 0, d, 0); if (z == 1) { if (i + 1 < n && i % k) upd(i + 1, j, 0, d, 0); if (j + 1 < m && j % k) upd(i, j + 1, 0, d, 0); } else if (z == 2) { if (i + 1 < n && i % k) upd(i + 1, j, 0, d, 0); if (j % k) upd(i, j - 1, 0, d, 0); } else if (z == 3) { if (i % k) upd(i - 1, j, 0, d, 0); if (j + 1 < m && j % k) upd(i, j + 1, 0, d, 0); } else { if (i % k) upd(i - 1, j, 0, d, 0); if (j % k) upd(i, j - 1, 0, d, 0); } } } cout << dd[encode(it, jt, 0)] << '\n'; return 0; }