Pond Skater

题目描述

水黾住在一个南北方向有 $H$ 行、东西方向有 $W$ 列的矩形网格状池塘中。从北往南第 $i$ 行、从西往东第 $j$ 列的格子记作 $(i,j)$。

字符 @ 表示该格子上有荷叶，水黾不能进入；字符 . 表示可以进入。

水黾每次划水可以向上、下、左、右任意一个方向移动不少于 $1$ 格且不多于 $K$ 格。移动过程中不能经过有荷叶的格子，也不能移动到有荷叶的格子或池塘外。

请计算从格子 $(x_1,y_1)$ 到格子 $(x_2,y_2)$ 最少需要划水多少次。如果无法到达，输出 -1。

输入格式

第一行包含三个整数 $H,W,K$。

第二行包含四个整数 $x_1,y_1,x_2,y_2$。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，描述池塘中的格子。

输出格式

输出一个整数，表示最少划水次数；如果无法到达，输出 -1。

样例输入 1

3 5 2
3 2 3 4
.....
.@..@
..@..

样例输出 1

5

样例输入 2

1 6 4
1 1 1 6
......

样例输出 2

2

样例输入 3

3 3 1
2 1 2 3
.@.
.@.
.@.

样例输出 3

-1

数据范围

对于所有测试点，保证 $1\le H,W,K\le 10^6$，$H\times W\le 10^6$，$1\le x_1,x_2\le H$，$1\le y_1,y_2\le W$，起点与终点不同，网格字符仅为 . 或 @，且起点、终点均为 .。