package main
import (
"io"
"os"
"strconv"
)
var parentRow []uint16
var parentCol []uint16
func nextInt(data []byte, p *int) int {
n := len(data)
for *p < n && data[*p] <= ' ' {
(*p)++
}
sign := 1
if *p < n && data[*p] == '-' {
sign = -1
(*p)++
}
val := 0
for *p < n {
c := data[*p]
if c < '0' || c > '9' {
break
}
val = val*10 + int(c-'0')
(*p)++
}
return val * sign
}
func nextToken(data []byte, p *int) []byte {
n := len(data)
for *p < n && data[*p] <= ' ' {
(*p)++
}
start := *p
for *p < n && data[*p] > ' ' {
(*p)++
}
return data[start:*p]
}
func findRow(base int, x uint16) uint16 {
for {
p := parentRow[base+int(x)]
if p == x {
return x
}
pp := parentRow[base+int(p)]
parentRow[base+int(x)] = pp
x = p
}
}
func findCol(base int, x uint16) uint16 {
for {
p := parentCol[base+int(x)]
if p == x {
return x
}
pp := parentCol[base+int(p)]
parentCol[base+int(x)] = pp
x = p
}
}
func main() {
data, _ := io.ReadAll(os.Stdin)
ptr := 0
n := nextInt(data, &ptr)
m := nextInt(data, &ptr)
k := nextInt(data, &ptr)
grid := make([][]byte, n)
for i := 0; i < n; i++ {
grid[i] = nextToken(data, &ptr)
}
x1 := nextInt(data, &ptr) - 1
y1 := nextInt(data, &ptr) - 1
x2 := nextInt(data, &ptr) - 1
y2 := nextInt(data, &ptr) - 1
if x1 == x2 && y1 == y2 {
os.Stdout.WriteString("0")
return
}
size := n * m
left := make([]uint16, size)
right := make([]uint16, size)
up := make([]uint16, size)
down := make([]uint16, size)
for i := 0; i < n; i++ {
row := grid[i]
base := i * m
for j := 0; j < m; {
if row[j] == '#' {
j++
continue
}
s := j
for j < m && row[j] == '.' {
j++
}
e := j - 1
lv := uint16(s + 1)
rv := uint16(e + 1)
for c := s; c <= e; c++ {
idx := base + c
left[idx] = lv
right[idx] = rv
}
}
}
for j := 0; j < m; j++ {
for i := 0; i < n; {
if grid[i][j] == '#' {
i++
continue
}
s := i
for i < n && grid[i][j] == '.' {
i++
}
e := i - 1
uv := uint16(s + 1)
dv := uint16(e + 1)
for r := s; r <= e; r++ {
idx := r*m + j
up[idx] = uv
down[idx] = dv
}
}
}
parentRow = make([]uint16, n*(m+2))
for i := 0; i < n; i++ {
base := i * (m + 2)
parentRow[base+m+1] = uint16(m + 1)
next := uint16(m + 1)
row := grid[i]
for j := m; j >= 1; j-- {
if row[j-1] == '.' {
parentRow[base+j] = uint16(j)
next = uint16(j)
} else {
parentRow[base+j] = next
}
}
parentRow[base] = next
}
parentCol = make([]uint16, m*(n+2))
for j := 0; j < m; j++ {
base := j * (n + 2)
parentCol[base+n+1] = uint16(n + 1)
next := uint16(n + 1)
for i := n; i >= 1; i-- {
if grid[i-1][j] == '.' {
parentCol[base+i] = uint16(i)
next = uint16(i)
} else {
parentCol[base+i] = next
}
}
parentCol[base] = next
}
dist := make([]int32, size)
queue := make([]int, size)
start := x1*m + y1
target := x2*m + y2
dist[start] = 1
queue[0] = start
head, tail := 0, 1
baseR := x1 * (m + 2)
cpos := uint16(y1 + 1)
parentRow[baseR+int(cpos)] = findRow(baseR, cpos+1)
baseC := y1 * (n + 2)
rpos := uint16(x1 + 1)
parentCol[baseC+int(rpos)] = findCol(baseC, rpos+1)
for head < tail {
cur := queue[head]
head++
nextDist := dist[cur] + 1
i := cur / m
j := cur % m
c := j + 1
l := c - k
if l < int(left[cur]) {
l = int(left[cur])
}
rr := c + k
if rr > int(right[cur]) {
rr = int(right[cur])
}
baseR = i * (m + 2)
col := findRow(baseR, uint16(l))
for int(col) <= rr {
nj := int(col) - 1
idx := i*m + nj
dist[idx] = nextDist
if idx == target {
os.Stdout.WriteString(strconv.Itoa(int(nextDist - 1)))
return
}
queue[tail] = idx
tail++
parentRow[baseR+int(col)] = findRow(baseR, col+1)
baseCC := nj * (n + 2)
rp := uint16(i + 1)
parentCol[baseCC+int(rp)] = findCol(baseCC, rp+1)
col = findRow(baseR, col)
}
r := i + 1
u := r - k
if u < int(up[cur]) {
u = int(up[cur])
}
dd := r + k
if dd > int(down[cur]) {
dd = int(down[cur])
}
baseC = j * (n + 2)
rowPos := findCol(baseC, uint16(u))
for int(rowPos) <= dd {
ni := int(rowPos) - 1
idx := ni*m + j
dist[idx] = nextDist
if idx == target {
os.Stdout.WriteString(strconv.Itoa(int(nextDist - 1)))
return
}
queue[tail] = idx
tail++
baseRR := ni * (m + 2)
cp := uint16(j + 1)
parentRow[baseRR+int(cp)] = findRow(baseRR, cp+1)
parentCol[baseC+int(rowPos)] = findCol(baseC, rowPos+1)
rowPos = findCol(baseC, rowPos)
}
}
os.Stdout.WriteString("-1")
}