#include <algorithm> #include <iostream> #include <cstring> #include <set> using namespace std; const int N = 6000000; const int N_ = 1 << 23; const int ddi[] = { -1, 0, 1, 0 }; const int ddj[] = { 0, 1, 0, -1 }; char tt[N + 1], *aa[N]; bool st[2][N_ << 1]; int n_; int *dd[N], qu[N * 2], head, cnt; int n, m; void pul(int z, int i) { int l = i << 1, r = l ^ 1; st[z][i] = st[z][l] || st[z][r]; } void pull(int z, int i) { while (i >>= 1) pul(z, i); } void build() { for (n_ = 1; n_ < n * m; n_ <<= 1) ; for (int z = 0; z < 2; z++) { for (int i = 0; i < n * m; i++) st[z][i + n_] = true; for (int i = n_ - 1; i; i--) pul(z, i); } } void update(int z, int i) { st[z][i += n_] = false, pull(z, i); } int search(int z, int l) { int r = n_ - 1; for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) if (l & 1) { if (st[z][l]) { while (l < n_) if (!st[z][l <<= 1]) l ^= 1; return l - n_; } l++; } return n_; } void assign(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; update(0, i * m + j); update(1, 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); build(); 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; assign(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); assign(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) { int ij = search(0, i_ * m + jl); if (ij > i_ * m + jr) break; assign(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) { int ji = search(1, j_ * n + il); if (ji > j_ * n + ir) break; assign(ji - j_ * n, j_, d + 1, 1); } } } } cout << ans << '\n'; return 0; }