#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[N], ii[N]; 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; } 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[i].insert(j); ii[j].insert(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[i_].lower_bound(jl); if (it == jj[i_].end()) break; j_ = *it; if (j_ > jr) break; update(i_, j_, d + 1, 1); jj[i_].erase(it); } } 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[j_].lower_bound(il); if (it == ii[j_].end()) break; i_ = *it; if (i_ > ir) break; update(i_, j_, d + 1, 1); ii[j_].erase(it); } } } } cout << ans << '\n'; return 0; }