/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
アメンボのすぬけ君は南北 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) まで移動することができない場合、そのことを指摘してください。
制約
- 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} =
. - 入力される数はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
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を出力せよ。
入力例 1
3 5 2 3 2 3 4 ..... .@..@ ..@..
出力例 1
5
はじめ、すぬけ君はマス (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) に移動する。
入力例 2
1 6 4 1 1 1 6 ......
出力例 2
2
入力例 3
3 3 1 2 1 2 3 .@. .@. .@.
出力例 3
-1
Score : 600 points
Problem Statement
Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.
Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..
In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.
Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.
Constraints
- 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 or y_1 \neq y_2.
- c_{i,j} is
.or@. - c_{x_1,y_1} =
. - c_{x_2,y_2} =
. - All numbers in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.
Sample Input 1
3 5 2 3 2 3 4 ..... .@..@ ..@..
Sample Output 1
5
Initially, Snuke is at the square (3,2). He can reach the square (3, 4) by making five strokes as follows:
-
From (3, 2), go west one square to (3, 1).
-
From (3, 1), go north two squares to (1, 1).
-
From (1, 1), go east two squares to (1, 3).
-
From (1, 3), go east one square to (1, 4).
-
From (1, 4), go south two squares to (3, 4).
Sample Input 2
1 6 4 1 1 1 6 ......
Sample Output 2
2
Sample Input 3
3 3 1 2 1 2 3 .@. .@. .@.
Sample Output 3
-1