//Template credits:
//Benq, Errichto and me
#include <bits/stdc++.h>
using namespace std;
#define i32 signed
#define int long long
using str = string; //yay python!
#define X first
#define Y second
using pii = pair<int,int>;
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define each(x,y) for(auto x : y)
#define sim template<class c
#define dor > dbg& operator<<
#define ris return *this
#define eni(x) sim> typename enable_if<sizeof dud<c>(0) x 1, dbg&>::type operator<<(c i)
sim> struct rge { c b,e; };
sim> rge<c> range(c i, c j) { return rge<c>{i,j}; }
sim> auto dud(c* x) -> decltype(cout << *x, 0);
sim> char dud(...);
template<class T, size_t R, size_t C>
struct matrik {
T (&arr)[R][C];
int r1, r2, c1, c2;
//pythonic: dim is either {r2, c2} or {r1, r2, c1, c2}
matrik(T (&a)[R][C], initializer_list<int> dims)
: arr(a), r1(0), r2(R), c1(0), c2(C)
{
auto it = dims.begin();
if (dims.size() == 2) {
r2 = *it++;
c2 = *it;
}
else if (dims.size() == 4) {
r1 = *it++;
r2 = *it++;
c1 = *it++;
c2 = *it;
}
}
};
sim, class b> ostream& operator<<(ostream &out, pair<b,c> d) {
out << "(" << d.X << ", " << d.Y << ")";
return out;
}
sim> ostream& operator<<(ostream &out, rge<c> d) {
out << "{";
f0r(it, d.b, d.e) out << ", " + 2*(it==d.b) << *it;
out << "}";
return out;
}
struct dbg {
//behaviour: it won't print spaces after debugging
~dbg() { cerr << '\n'; }
eni(!=) { // for non-iterables
cerr << boolalpha << i; ris;
}
eni(==) { // for iterables
ris << range(all(i));
}
// pair printer
sim, class b dor(pair<b,c> d) {
ris << "(" << d.X << ", " << d.Y << ")";
}
// range printer (should work for like most c++ stuffs)
sim dor(rge<c> d) {
*this << "{";
f0r(it, d.b, d.e) *this << ", " + 2*(it==d.b) << *it;
ris << "}";
}
sim, size_t R, size_t C dor(const matrik<c,R,C>& m) {
int rows = m.r2 - m.r1;
int cols = m.c2 - m.c1;
//ts only works for immediate printables...rip
std::vector<int> w(cols, 0);
for (int j = 0; j < cols; ++j)
for (int i = 0; i < rows; ++i) {
std::ostringstream buf;
buf << m.arr[m.r1 + i][m.c1 + j];
w[j] = std::max(w[j], (int)buf.str().size());
}
*this << "[";
for (int i = 0; i < rows; ++i) {
if (i) cerr << ",\n ";
cerr << "[";
for (int j = 0; j < cols; ++j) {
if (j) cerr << ", ";
cerr << setw(w[j]) // right-justify to column width
<< m.arr[m.r1 + i][m.c1 + j];
}
cerr << "]";
}
ris << "]";
}
//3 tuple example
sim, class d, class e dor(const tuple<c,d,e>& t) {
ris << "(" << get<0>(t) << ", "
<< get<1>(t) << ", " << get<2>(t) << ")";
}
};
#define imie(r...) " [" << #r << ": " << (r) << "] "
sim, size_t depth>
struct _nvt {
using type = vt<typename _nvt<c,depth-1>::type>;
};
sim>
struct _nvt<c,1> {
using type = vt<c>;
};
sim, size_t depth>
using nvt = typename _nvt<c,depth>::type;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
//do not forget to invert priority queue comparisons
//never forget the cf "the way home" incident
template<class T> using pqm = priority_queue<T, vector<T>, greater<T>>;
constexpr int pct(int x) { return __builtin_popcountll((unsigned long long)x); }
//this is more mathematically cool than you think
//it should work for o(1) range max queries
//p2(bits(x)) returns the highest power of 2 <= x
constexpr int bits(int x) { return x == 0 ? 0 : 63 - __builtin_clzll((unsigned long long)x); }
constexpr int p2(int x) { return (int)1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
inline long long cdiv(long long a, long long b) { return a / b + ((a ^ b) > 0 && a % b); }
inline long long fdiv(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
//olympiad (ts is so tuff bro)
template<class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<class T, class U> T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); while(lo < hi) { T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; }
template<class T, class U> T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); while(lo < hi) { T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; }
template<class T> void remDup(vector<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); }
//never forget the aiio 2013 RJ incident
template<class T, class U> void safeErase(T &t, const U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
const auto beg_time = chrono::high_resolution_clock::now();
double time_elapsed() { return chrono::duration<double>(chrono::high_resolution_clock::now() - beg_time).count(); }
int d4i[4] = {0,0,1,-1};
int d4j[4] = {1,-1,0,0};
//get d4i and d4j stuff down
i32 main() {
cin.tie(0)->sync_with_stdio(0);
int r,c,n;
int sr,sc,gr,gc;
cin>>r>>c>>n>>sr>>sc>>gr>>gc;
sr--,sc--,gr--,gc--;
nvt<bool,2> maze = vt(r,vt(c,true));
f0r(i,0,r) {
f0r(j,0,c) {
char x;cin>>x;
if(x=='.') {
maze[i][j] = 0;
} else {
}
}
}
pqm<pair<int,pii>> bfs;
bfs.push({0,{sr,sc}});
nvt<int,2> mnd = vt(r,vt(c,(int)1e9));
mnd[sr][sc] = 0;
while(sz(bfs)) {
auto fr = bfs.top();
auto [x,y] = fr.Y;
bfs.pop();
f0r(g,0,4) {
int nx = x+d4i[g], ny = y+d4j[g];
if(nx >= 0 and nx < r and ny >= 0 and ny < c) {
if(mnd[x][y]+maze[x][y] < mnd[nx][ny]) {
mnd[nx][ny] = mnd[x][y]+maze[x][y];
bfs.push({mnd[nx][ny], {nx,ny}});
}
}
}
}
cout << mnd[gr][gc] << '\n';
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* on easy problems: it's usually an easy bug
* work probabilistically and be rational
* don't trip on specific code if you're sure of it:
* either your logic is provably wrong
* or you misread the problem
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
/*
Debugging toolkit
* if you proved the correctness of a DP/Greedy approach,
using an imagined case, you're likely wrong.
* if you skim read the problem to get the "gist" of it and then
start cooking up a "too easy" approach, you're almost certainly wrong.
* You shouldn't be reasoning about a block of code for more than 30s:
keep your ideas fresh.
* Do not skip over bits of code, especially pertaining pronumerals,
just because it "looks correct". Spend 30s reasoning about it, then
move on.
*/
