#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define vi vector<int> #define vs vector<string> #define vb vector<bool> #define vpi vector<pi> #define pb push_back #define all(a) (a).begin(), (a).end() const int mod = 1e9 + 7; int n, r, c; vector<vi> grid, dist, vis; signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> r >> c >> n; grid.resize(r, vi(c)); dist.resize(r, vi(c, mod)); vis.resize(r, vi(c, 0)); pi st, fn; cin >> st.first >> st.second >> fn.first >> fn.second; st.first--; st.second--; fn.first--; fn.second--; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { char c; cin >> c; grid[i][j] = (c == '#'); } } dist[st.first][st.second] = grid[st.first][st.second]; vis[st.first][st.second] = 1; vpi moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; queue<pi> q; q.push(st); while (q.size()) { auto p = q.front(); // cout << p.first << ' ' << p.second << '\n'; q.pop(); for (auto mv : moves) { pi m = make_pair((p.first + mv.first), (p.second + mv.second)); if (!(m.first >= 0 && m.second >= 0 && m.first < r && m.second < c) || vis[m.first][m.second]) continue; vis[m.first][m.second] = 1; q.push(m); int mn = mod; if (grid[st.first][st.second] && (abs(st.first - m.first) < n && abs(st.second - m.second) < n)) { dist[m.first][m.second] = 1; if (m == fn) { cout << dist[fn.first][fn.second] << '\n'; return 0; } continue; } if (grid[m.first][m.second] == 0) { if (m.first - 1 >= 0) mn = min(mn, dist[m.first - 1][m.second]); if (m.second - 1 >= 0) mn = min(mn, dist[m.first][m.second - 1]); if (m.first + 1 < r) mn = min(mn, dist[m.first + 1][m.second]); if (m.second - 1 < c) mn = min(mn, dist[m.first][m.second + 1]); dist[m.first][m.second] = mn; if (m == fn) { cout << dist[fn.first][fn.second] << '\n'; return 0; } continue; } map<pi, int> mp; queue<pi> q2; q2.push(m); mp[m] = 1; while (q2.size()) { auto p2 = q2.front(); q2.pop(); mn = min(mn, dist[p2.first][p2.second]); for (auto mv2 : moves) { pi m2 = make_pair((p2.first + mv2.first), (p2.second + mv2.second)); if (!(m2.first >= 0 && m2.second >= 0 && m2.first < r && m2.second < c) || mp[m2]) continue; mp[m2] = 1; if (abs(m.first - m2.first) <= n && abs(m.second - m2.second) <= n && !(abs(m.first - m2.first) == n && abs(m.second - m2.second) == n)) q2.push(m2); } } dist[m.first][m.second] = min(dist[m.first][m.second], mn + 1); if (m == fn) { cout << dist[fn.first][fn.second] << '\n'; return 0; } } } }