F - Pond Skater

Contest Duration: 2020-06-14(Sun) 12:00 - 2020-06-14(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Pond Skater Editorial

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を出力せよ。

入力例 1Copy

Copy

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

出力例 1Copy

Copy

はじめ、すぬけ君はマス $(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)$ に移動する。

入力例 2Copy

Copy

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

出力例 2Copy

Copy

入力例 3Copy

Copy

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

出力例 3Copy

Copy

-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 1Copy

Copy

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

Sample Output 1Copy

Copy

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 2Copy

Copy

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

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy

-1