题目描述
【题目背景】
乘其阴乱，利其弱而无主。随，以向晦入宴息。
33DAI 来到了一个大水塘抓鱼。可以把大水塘看作是一个 $n$ 行 $m$ 列的二维字符数组。第 $x$ 行第 $y$ 列的字符是 $a_{x,y}$。如果字符是 `.` 则表示是在正常水域，如果字符是 `@` 则表示有大石头不能通行。
33DAI 初始在第 $x_1$ 行 $y_1$ 列。 他要抓的鱼在第 $x_2$ 行第 $y_2$ 列。他每次移动可以往上下左右四个方向之一走 $1\sim k$ 步（假设走了 $x$ 步，则必须保证包括起点和终点及路程中的所有点这 $x+1$ 个位置都不能是大石头）。请问他最少几次移动可以到达鱼的位置。如果无法走到，输出 $-1$。
输入
第一行三个整数，$n,m,k$。
第二行四个整数，$x_1,y_1,x_2,y_2$。
接下来 $n$ 行每行 $m$ 列，第 $i$ 行第 $j$ 列为 $a_{i,j}$。
输出
输出一个整数，即 33DAI 最少几次移动可以到达鱼的位置。如果无法走到，输出 $-1$。
样例输入输出
输入#1
复制
3 5 2
3 3 3 5
@....
..@@.
@..@.
7 7 4
1 1 7 7
.......
.......
.......
.......
.......
.......
.......
输入#2
复制
7 7 4
1 1 7 7
.......
.......
.......
.....@.
....@.@
....@..
.....@.
提示
【样例1解释】
移动路线可以为：$(3,3),(3,2),(1,2),(1,3),(1,5),(3,5)$，一共移动了 $5$ 步。
【样例2解释】
移动路线可以为：$(1,1),(1,3),(1,7),(4,7),(7,7)$，一共移动了 $4$ 步。
【样例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\neq x_2$ 或者 $y_1\neq y_2$
- $a_{i,j}$ 为 `.` 或 `@`
- 保证 $a_{x1,y1}$ 和 $a_{x2,y2}$ 都不是 `@`
子任务划分：
- 子任务 1（10 分）：保证 $n=1$
- 子任务 2（20 分）：保证 $n,m\le 1000$ 且 $k=1$
- 子任务 3（30 分）：保证 $k=1$
- 子任务 4（40 分）：没有特殊限制