#include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<long long, long long> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' #define ld long double #define sz(x) static_cast<int>((x).size()) #define i5 tuple<int,int,int,int,int> #define all(x) x.begin(), x.end() #define iiii tuple<int, int,int,int> signed main(){ int r, c, n;cin>>r>>c>>n; int sr,sc,gr,gc;cin>>sr>>sc>>gr>>gc; vector<vector<bool>> mat(r+2, vector<bool>(c+2, 0)), vis0(r+2, vector<bool>(c+2, 0)), vis1(r+2, vector<bool>(c+2, 0)); vector<vector<int>> d(r+2, vector<int>(c+2, -1)); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ char c;cin>>c; if(c=='.')mat[i][j]=1; } } vector<pll> cur; cur.pb({sr, sc}); d[sr][sc]=0; int dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; auto out=[&](int x, int y)->bool{return ((x < 1) or (x > r) or (y < 1) or (y > c));}; int cd=0; while(!cur.empty()){ vector<pll> b; // do 0-1 bfs from every cell in b for (auto [x, y] : cur){ queue<pll> q; q.push({x, y}); vis0[x][y]=true; while(!q.empty()){ auto [i, j] = q.front(); q.pop(); //printf("%lld %lld \n", i, j); for(int k=0;k<4;k++){ int di=dir[k][0], dj=dir[k][1]; int ni=i+di, nj=j+dj; //printf("di %lld dj %lld, ni %lld nj %lld\n", di, dj, ni, nj); if (out(ni, nj) or vis0[ni][nj]){ continue; } if (!mat[ni][nj]) { b.pb({ni, nj}); d[ni][nj]=d[i][j]+1; } else { q.push({ni, nj}); d[ni][nj]=d[i][j]; } vis0[ni][nj]=true; } } } /*printf("cd %lld, border cells are \n", cd); for(auto [i, j] : b){ printf("(%lld, %lld) ", i, j); } cout<<endl;*/ for(int k=0;k<4;k++){ int di=dir[k][0], dj=dir[k][1]; vector<pll> nw, lay=b; for(int t=0;t<n-1;t++){ vector<pll> nxtlay; for(auto [i, j] : lay){ int ni=i+di, nj=j+dj; if(out(ni, nj) or vis0[ni][nj])continue; vis0[ni][nj]=true; d[ni][nj]=cd+1; nw.pb({ni, nj}); nxtlay.pb({ni, nj}); } swap(nxtlay, lay); } b.insert(b.end(),all(nw)); } swap(cur, b); cd++; } cout<<d[gr][gc]; }