抓鱼

题目描述

小珅来到了一个大水塘抓鱼。可以把大水塘看作是一个 $n$ 行 $m$ 列的二维字符数组。第 $x$ 行第 $y$ 列的字符是 $a_{x,y}$。如果字符是 . 则表示是在正常水域，如果字符是 @ 则表示有大石头不能通行。

小珅初始在第 $x_1$ 行 $y_1$ 列。他要抓的鱼在第 $x_2$ 行 $y_2$ 列。他每次移动可以往上下左右四个方向之一走 $1 \sim k$ 步（假设走了 $t$ 步，则必须保证包括起点和终点及路程中的所有点这 $t+1$ 个位置都不能是大石头）。请问他最少几次移动可以到达鱼的位置。如果无法走到，输出 $-1$。

输入格式

第一行三个整数 $n, m, k$。

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

接下来 $n$ 行每行 $m$ 列，第 $i$ 行第 $j$ 列为 $a_{i,j}$。

输出格式

输出一个整数，即小珅最少几次移动可以到达鱼的位置。如果无法走到，输出 $-1$。

输入输出样例

输入 #1

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

输出 #1

5

输入 #2

7 7 4
1 1 7 7
.......
.......
.......
.......
.......
.......
.......

输出 #2

4

输入 #3

7 7 4
1 1 7 7
.......
.......
.......
.....@.
....@.@
....@..
.....@.

输出 #3

-1

说明/提示

对于 $100\%$ 的数据：

$1 \le n, m, k \le 10^6$

$1 \le n \times m \le 10^6$

$1 \le x_1, x_2 \le n$，$1 \le y_1, y_2 \le m$

$x_1 \ne x_2$ 或 $y_1 \ne y_2$

$a_{i,j}$ 为 . 或 @

保证 $a_{x_1,y_1}$ 和 $a_{x_2,y_2}$ 都不是 @

子任务 $1$（$10$ 分）：保证 $n = 1$。

子任务 $2$（$20$ 分）：保证 $n, m \le 1000$ 且 $k = 1$。

子任务 $3$（$30$ 分）：保证 $k = 1$。

子任务 $4$（$40$ 分）：没有特殊限制。