6796: 富哥爱游泳
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：14
解决：5
题目描述
富哥这天在一个$H*W$大小的池塘里游泳，有一些方格是@则代表该方格有一片荷叶，富哥游不过去。
现在岸边的$mhgg$让富哥从$(x_1,y_1)$游到$(x_2,y_2)$且换气最少，由于富哥肺活量有限而且是闭着眼游的，所以他一口气最多只能朝一个方向(上下左右)游$K$格,并且不能游出池塘或游过荷叶。
现在请你算出付哥最少需要换气几下达到目标点。
现在岸边的$mhgg$让富哥从$(x_1,y_1)$游到$(x_2,y_2)$且换气最少，由于富哥肺活量有限而且是闭着眼游的，所以他一口气最多只能朝一个方向(上下左右)游$K$格,并且不能游出池塘或游过荷叶。
现在请你算出付哥最少需要换气几下达到目标点。
输入
$H$ $W$ $K$
$x_1$ $y_1$ $x_2$ $y_2$
$c_{1,1}$$c_{1,2}$$..$$c_{1,W}$
$c_{2,1}$$c_{2,2}$$..$$c_{2,W}$
$...$
$c_{H,1}$$c_{H,2}$$..$$c_{H,W}$
$x_1$ $y_1$ $x_2$ $y_2$
$c_{1,1}$$c_{1,2}$$..$$c_{1,W}$
$c_{2,1}$$c_{2,2}$$..$$c_{2,W}$
$...$
$c_{H,1}$$c_{H,2}$$..$$c_{H,W}$
- $ 1\ \leq\ H,W,K\ \leq\ 10^6 $
- $ H\ \times\ W\ \leq\ 10^6 $
- $ 1\ \leq\ x_1,x_2\ \leq\ H $
- $ 1\ \leq\ y_1,y_2\ \leq\ W $
- $ x_1\ \neq\ x_2 $ 或者 $ y_1\ \neq\ y_2 $
- $ c_{i,j} $ 为 '.' 或者 '@'
-
$ c_{x_1,y_1}\ = $ '.'
- $ c_{x_2,y_2}\ = $ '.'
输出
最小换气次数$($如果无法到达输出$-1$$)$
样例输入 复制
3 5 2
3 2 3 4
.....
.@..@
..@..
样例输出 复制
5