#include <iostream> #include <iomanip> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <stack> #include <bitset> #include <string> #include <cstring> #include <iterator> #include <random> #include <unordered_map> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef long double ld; const ll dim=1e6 + 10; const ll mod=998244353; const ll inf=1e18+77; //#define endl "\n" #define fi first #define pb push_back #define se second #define vll vector<ll> ll n,t; vector<vll> g, vis; ll a[dim]; ll m; ll r, c; queue<pll> q1, q2; struct state{ ll val, h, v; }; ll fl=0; vector<vector<state> > dst; void check(ll x, ll y, ll val, ll h, ll v, ll tp){ if(x<1 || x>r || y<1 || y>c)return; if(dst[x][y].val<=val)return; dst[x][y]={val, h, v}; if(tp==0){fl=1; q1.push({x, y});} else q2.push({x, y}); } void check1(ll x, ll y, ll val, ll h, ll v){ if(x<1 || x>r || y<1 || y>c)return; if(g[x][y]==1){ check(x, y, val+1, n-1, n-1, 1); } else{ check(x, y, val, 0, 0, 0); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //cin>>t; t=1; while(t--){ cin>>r>>c>>n; ll p1, p2, x, y; //ll u1, u2; char ch; cin>>p1>>p2; cin>>x>>y; g.assign(r+6, vll(c+6, 0)); vis.assign(r+6, vll(c+6, 0)); dst.assign(r+6, vector<state>(c+6, {r*c+100,0, 0})); for(int i=1; i<=r; i++) { for(int j=1; j<=c; j++){ cin>>ch; g[i][j]=(ch=='#'); // cout<<g[i][j]<<" "; } //cout<<endl; } check1(p1, p2,0, 0, 0); while(q1.size()>0){ auto [u1, u2]=q1.front(); fl=0; // cout<<u1<<" "<<u2<<endl; state cur=dst[u1][u2]; // cout<<cur.val<<" "<<cur.h<<" "<<cur.v<<endl; q1.pop(); if(cur.v>0) { check(u1 - 1, u2, cur.val, cur.h, cur.v - 1, 0); check(u1 + 1, u2, cur.val, cur.h, cur.v - 1, 0); } if(cur.h>0) { check(u1, u2 - 1, cur.val, cur.h - 1, cur.v, 0); check(u1, u2 + 1, cur.val, cur.h - 1, cur.v, 0); } // if(cur.h==0 || cur.v==0){ if(fl==0){ check1(u1 - 1, u2, cur.val, cur.h, cur.v); check1(u1 + 1, u2, cur.val, cur.h, cur.v ); check1(u1, u2 - 1, cur.val, cur.h , cur.v); check1(u1, u2 + 1, cur.val, cur.h , cur.v); } //} if(q1.size()==0){ q1=q2; while(q2.size()>0)q2.pop(); } } if(dst[x][y].val==(r*c+100))while(1); cout<<dst[x][y].val<<endl; } return 0; }