题目描述

アメンボのすぬけ君は南北 $H$ マス東西 $W$ マスの長方形の形をしたグリッド状の池に住んでいます。北から $i$ 番目、西から $j$ 番目のマスをマス $(i,j)$ とします。

いくつかのマスには蓮の葉が浮かんでおり、すぬけ君はそれらのマスには入ることができません。 $c_{ij}$ が @ のときマス $(i,j)$ に蓮の葉が浮かんでいること、.のときそうでないことを表します。

すぬけ君は一回水をかくことで東西南北のいずれかの方向に $1$ マス以上 $K$ マス以下移動することができます。 移動の途中に蓮の葉のあるマスがあってはいけません。また、蓮の葉のあるマスや池の外に移動することもできません。

すぬけ君がマス $(x_1,y_1)$ から $(x_2,y_2)$ まで移動するのに最小で何回水をかく必要があるか求めてください。 $(x_1,y_1)$ から $(x_2,y_2)$ まで移動することができない場合、そのことを指摘してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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)$ まで移動するのに必要な最小の水かきの回数を出力せよ。 $(x_1,y_1)$ から $(x_2,y_2)$ まで移動することができない場合、-1を出力せよ。

题目大意

你在一个划分为上下 $H$ 行，左右 $W$ 列的长方形网格中，网格从上到下的第 $i$ 行的从左往右第 $j$ 列被编号为 $(i,j)$ ，如果 $c_{i,j}$ 为 @ ，则 $(i,j)$ 不能通过。

你现在在 $(x_1,y_1)$，你每步可以往上下左右走 $1$ 至 $K$ 格，问你最少需要多少步才能走到 $(x_2,y_2)$ ，如果不能走到，输出 $-1$ 。

输入先是一行三个整数 $H,W,K$ ，再是一行四个整数 $x_1,y_1,x_2,y_2$，接着是 $H \times W$ 的字符矩阵，第 $i$ 行 $j$ 列表示 $c_{i,j}$ 。

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

5

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

2

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

-1

提示

制約

• $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}\ =$ .
• 入力される数はすべて整数である。

Sample Explanation 1

はじめ、すぬけ君はマス $(3,2)$ にいます。 以下のように $5$ 回水をかくことでマス $(3,4)$ まで移動することができます。 - マス $(3,2)$ から西に $1$ マス進み、マス $(3,1)$ に移動する。 - マス $(3,1)$ から北に $2$ マス進み、マス $(1,1)$ に移動する。 - マス $(1,1)$ から東に $2$ マス進み、マス $(1,3)$ に移動する。 - マス $(1,3)$ から東に $1$ マス進み、マス $(1,4)$ に移動する。 - マス $(1,4)$ から南に $2$ マス進み、マス $(3,4)$ に移動する。