← Home
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")
}