#include<bits/stdc++.h> using namespace std; #define inf (int)2e9 #define _ <<' '<< #define nl '\n' void solve(){ int r, c, n, sx, sy, ex, ey; cin>>r>>c>>n>>sx>>sy>>ex>>ey; sx--, sy--, ex--, ey--; set<int> sr[r], sc[c]; int a[r][c]; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ char s; cin>>s; a[i][j] = (s == '#'); sr[i].insert(j); sc[j].insert(i); } } deque<tuple<int,int,int>> dq; vector d(r, vector(c, inf)); dq.push_back({0, sx, sy}); d[sx][sy] = 0; while(!dq.empty()){ auto [dis, x, y] = dq.front(); dq.pop_front(); if(dis != d[x][y]) continue; if(x == ex and y == ey){ cout<<dis; return; } auto f = [&](int w, int nx, int ny){ if(dis + w >= d[nx][ny]) return; d[nx][ny] = dis + w; if(w) dq.push_back({dis+1, nx, ny}); else dq.push_front({dis, nx, ny}); }; if(x-1 >= 0 and !a[x-1][y]) f(0, x-1, y); if(x+1 < r and !a[x+1][y]) f(0, x+1, y); if(y-1 >= 0 and !a[x][y-1]) f(0, x, y-1); if(y+1 < c and !a[x][y+1]) f(0, x, y+1); int dx = abs(x - ex); int dy = abs(y - ey); if(min(dx, dy) < n and max(dx, dy) <= n) f(1, ex, ey); auto row = [&](int z){ auto il = sr[z].upper_bound(y-n); auto ir = sr[z].lower_bound(y+n); if(il == sr[z].end() or sr[z].empty() or ir == sr[z].begin()) return; int l = *il; int r = *--ir; for(int i = l; i <= r; i++){ f(1, z, i); sr[z].erase(i); } }; auto col = [&](int z){ auto il = sc[z].upper_bound(x-n); auto ir = sc[z].lower_bound(x+n); if(il == sc[z].end() or sc[z].empty() or ir == sc[z].begin()) return; int l = *il; int r = *--ir; for(int i = l; i <= r; i++){ f(1, i, z); sc[z].erase(i); } }; if(x-n >= 0) row(x-n); if(x+n < r) row(x+n); if(y-n >= 0) col(y-n); if(y+n < c) col(y+n); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); return 0; }