#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 6e6 + 10, block = sqrt(maxn) + 10;
struct cell
{
int x, y;
cell(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
cell add(const cell &r) const
{
cell d;
d.x = x + r.x;
d.y = y + r.y;
return d;
}
};
cell neib[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int n, m, h;
vector < int > a[block], par[block];
vector < int > l[block], r[block], fict[block];
vector < int > used[block], ver_idx[block];
vector < pair < int, bool > > adj[maxn];
int stx, sty, enx, eny;
int find_leader(int i, int j)
{
if (par[i][j] == j)
return j;
return (par[i][j] = find_leader(i, par[i][j]));
}
void unite(int x, int y, int i, int j)
{
y = find_leader(x, y);
j = find_leader(i, j);
if (y == j)
return;
l[i][j] = min(l[i][j], l[x][y]);
r[i][j] = max(r[i][j], r[x][y]);
par[x][y] = j;
}
int nxt;
int build(int row, int left, int right)
{
if (left == right)
return ver_idx[row][left];
int mid = (left + right) / 2;
int lf = build(row, left, mid);
int rf = build(row, mid + 1, right);
nxt ++;
adj[nxt].push_back({lf, 0});
adj[nxt].push_back({rf, 0});
return nxt;
}
void add_edges(int root, int left, int right, int qleft, int qright, int ver, int val)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
adj[ver].push_back({root, val});
return;
}
int mid = (left + right) / 2;
add_edges(adj[root][0].first, left, mid, qleft, qright, ver, val);
add_edges(adj[root][1].first, mid + 1, right, qleft, qright, ver, val);
}
int row_root[block];
int visit[maxn], dist[maxn];
int col_root[maxn];
int build_col(int col, int left, int right)
{
if (left == right)
return ver_idx[left][col];
int mid = (left + right) / 2;
int lf = build_col(col, left, mid);
int rf = build_col(col, mid + 1, right);
nxt ++;
adj[nxt].push_back({lf, 0});
adj[nxt].push_back({rf, 0});
return nxt;
}
void solve()
{
cin >> n >> m >> h;
cin >> stx >> sty;
cin >> enx >> eny;
for (int i = 1; i <= n; i ++)
{
a[i].resize(m + 2);
l[i].resize(m + 2);
r[i].resize(m + 2);
par[i].resize(m + 2);
used[i].resize(m + 2);
fict[i].resize(m + 2);
ver_idx[i].resize(m + 2);
for (int j = 1; j <= m; j ++)
{
l[i][j] = r[i][j] = j;
par[i][j] = j;
used[i][j] = -1;
}
for (int j = 1; j <= m; j ++)
{
char c;
cin >> c;
if (c == '.')
a[i][j] = 0;
else
a[i][j] = 1;
}
}
int cnt = 0;
nxt = n * m;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
ver_idx[i][j] = ++ cnt;
}
}
for (int i = 1; i <= n; i ++)
row_root[i] = build(i, 1, m);
for (int j = 1; j <= m; j ++)
{
for (int i = 1; i <= n; i ++)
{
int left = max(1, j - h), right = min(m, j + h);
fict[i][j] = ++ nxt;
///add_edges(row_root[i], 1, m, left, right, fict[i][j], 0);
}
/**for (int i = 1; i <= n; i ++)
cout << fict[i][j] << " ";
cout << endl;*/
col_root[j] = build_col(j, 1, n);
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
cell cur(i, j);
for (int d = 0; d < 4; d ++)
{
cell nb = cur.add(neib[d]);
if (nb.x > 0 && nb.x <= n && nb.y > 0 && nb.y <= m)
if (a[nb.x][nb.y] == 0)
{
adj[ver_idx[cur.x][cur.y]].push_back({ver_idx[nb.x][nb.y], 0});
}
}
int st_row = max(1, i - h), en_row = min(n, i + h);
int st_col = max(1, j - h), en_col = min(m, j + h);
int fs_row = st_row, ds_row = en_row;
if (fs_row == i - h)
fs_row ++;
if (ds_row == i + h)
ds_row --;
///cout << i << " " << j << " range " << st_row << " " << en_row << endl;
///add_edges(col_root[j], 1, n, fs_row, ds_row, ver_idx[i][j], 1);
if (st_row == i - h)
{
if (st_col == j - h)
st_col ++;
if (en_col == j + h)
en_col --;
}
add_edges(row_root[st_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
if (st_row == i - h)
{
if (st_col == j - h)
st_col --;
if (en_col == j + h)
en_col ++;
}
if (en_row == i + h)
{
if (st_col == j - h)
st_col ++;
if (en_col == j + h)
en_col --;
}
////cout << i << " " << j << " range " << st_col << " " << en_col << endl;
add_edges(row_root[en_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
if (en_row == i + h)
{
if (st_col == j - h)
st_col --;
if (en_col == j + h)
en_col ++;
}
if (st_col == j - h)
{
if (st_row == i - h)
st_row ++;
if (en_row == i + h)
en_row --;
}
add_edges(col_root[st_col], 1, n, st_row, en_row, ver_idx[i][j], 1);
if (st_col == j - h)
{
if (st_row == i - h)
st_row --;
if (en_row == i + h)
en_row ++;
}
if (en_col == j + h)
{
if (st_row == i - h)
st_row ++;
if (en_row == i + h)
en_row --;
}
add_edges(col_root[en_col], 1, n, st_row, en_row, ver_idx[i][j], 1);
if (en_col == j + h)
{
if (st_row == i - h)
st_row --;
if (en_row == i + h)
en_row ++;
}
/**for (int row = st_row; row <= en_row; row ++)
{
if (row == i - h || row == i + h)
{
st_col ++, en_col --;
add_edges(row_root[row], 1, m, st_col, en_col, ver_idx[i][j], 1);
st_col --, en_col ++;
}
else
{
adj[ver_idx[cur.x][cur.y]].push_back({fict[row][cur.y], 1});
}
}*/
}
for (int i = 1; i <= nxt; i ++)
dist[i] = 1e9;
deque < int > dq;
dq.push_back(ver_idx[stx][sty]);
dist[ver_idx[stx][sty]] = 0;
while(!dq.empty())
{
int cur = dq.front();
dq.pop_front();
for (pair < int, int > nb : adj[cur])
{
int u = nb.first;
int w = nb.second;
if (dist[u] > dist[cur] + w)
{
dist[u] = dist[cur] + w;
if (w == 0)
dq.push_front(u);
else
dq.push_back(u);
}
}
}
for (int i = 1; i <= n; i ++, cout << endl)
for (int j = 1; j <= m; j ++)
cout << dist[ver_idx[i][j]] << " ";
int ans = dist[ver_idx[enx][eny]];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (abs(i - enx) <= h && abs(j - eny) <= h)
{
if (abs(i - enx) + abs(j - eny) != 2 * h)
{
ans = min(ans, dist[ver_idx[i][j]] + 1);
}
}
}
cout << ans << endl;
}
int main()
{
speed();
solve();
return 0;
}
