#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define st first #define nd second #define f(a, c, b) for (int a = c; b > a; a++) #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) int(a.size()) #define int ll #define DUZO 1000000000000000000 using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vvi = vector<vector<int>>; int n, m, k; int ys, xs; int yk, xk; vvi a; vvi o; vector<pii> otoczka; vector<pii> ruchy = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vector<pii> skos = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int aktl_wnk = 0; bool wolne(int y, int x) { if (min(y, x) < 0) return false; if (y >= n || x >= m) return false; if (o[y][x]) return false; return (!(a[y][x])); } bool zajete(int y, int x) { if (min(y, x) < 0) return false; if (y >= n || x >= m) return false; if (o[y][x]) return false; return (a[y][x]); } bool nie_odw(int y, int x) { if (min(y, x) < 0) return false; if (y >= n || x >= m) return false; if (o[y][x]) return false; return true; } void nowa_otoczka() { aktl_wnk++; vector<pii> no; for (auto [y, x]: otoczka) { for (pii ele: ruchy) { int ny = y + ele.st; int nx = x + ele.nd; if (ny == yk && nx == xk) { cout << aktl_wnk; exit(0); } if (nie_odw(ny, nx)) { o[ny][nx] = 1; a[ny][nx] = 0; no.pb({ny, nx}); } } } otoczka = no; /*cout << "otoczka po noramalnym rozszerzeniu:\n"; for (pii ele: otoczka) { cout << ele.st << " " << ele.nd << "\n"; } cout << "\n";*/ f(i, 1, k) { vector<pii> no; for (auto [y, x]: otoczka) { //cout << "jestem w " << y << " " << x << "\n"; for (pii ele: skos) { int ny = y + ele.st; int nx = x + ele.nd; if (ny == yk && xk == nx) { cout << aktl_wnk << "\n"; exit(0); } if (nie_odw(ny, nx)) { //cout << "moje czystki przetrwal kandydat " << ny << " " << nx << "\n"; o[ny][nx] = 1; a[ny][nx] = 1; no.pb({ny, nx}); } } //cout << "\n"; } otoczka = no; } } void bfs() { //majac do dyspozycji otoczke int ind = 0; while (sz(otoczka) > ind) { pii p = otoczka[ind]; int y = p.st; int x = p.nd; if (y == yk && x == xk) { cout << aktl_wnk << "\n"; exit(0); } ind++; o[y][x] = 1; for (pii ele: ruchy) { int ny = y + ele.st; int nx = x + ele.nd; if (!wolne(ny, nx)) continue; o[ny][nx] = 1; otoczka.pb({ny, nx}); } } vector<pii> no; for (auto [y, x]: otoczka) { for (pii ele: ruchy) { int ny = y + ele.st; int nx = x + ele.nd; if (zajete(ny, nx)) {no.pb({y, x}); break;} } } otoczka = no; } void solve() { cin >> n >> m >> k >> ys >> xs >> yk >> xk; ys--; xs--; yk--; xk--; a.resize(n, vi(m)); o.resize(n, vi(m, 0)); f(i, 0, n) { f(j,0, m) { char z; cin >> z; if (z == '.') a[i][j] = 0; else a[i][j] = 1; } } otoczka.pb({ys, xs}); while (true) { bfs(); /*cout << "po iteracji " << aktl_wnk << " nowa otoczka to:\n"; for (pii ele: otoczka) { cout << ele.st << " " << ele.nd << "\n"; } cout << "\n";*/ nowa_otoczka(); /*cout << "po rozszerzaniu zamieniamy to otoczke na:\n"; for (pii ele: otoczka) { cout << ele.st << " " << ele.nd << "\n"; } cout << "\n";*/ } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int q = 1; //cin >> q; while (q--) solve(); return 0; }