Pond Skater

题目描述

Snuke（一只水黾）生活在一个矩形的池塘中，该池塘可以视为有 $H$$$东西向行和 $W$$$南北向列的网格。记 $(i,j)$ 为从北向下第 $i$$行、从西向右第$j$$$列的格子。 有些格子上有荷叶，不能进入。 当$c_{ij}$为$@$时，格子$(i,j)$上有荷叶；当$c_{ij}$为$.$ 时，则没有。 在一次划动中，Snuke 可以朝四个方向之一（北、东、南、西）移动 $1$ 到 $K$ 格（含端点）。 移动时不得穿过有荷叶的格子。移动到有荷叶的格子或池塘外也是禁止的。 求 Snuke 从格子 $(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}$

输出格式

输出 Snuke 从格子 $(x_1,y_1)$ 到 $(x_2,y_2)$ 所需的最小划动次数；如果无法到达则输出 $-1$。

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$ 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.最初，Snuke 在格子 $(3,2)$。 他可以通过以下五次划动到达格子 $(3,4)$：

从 $(3, 2)$ 向西走一格到 $(3, 1)$。

从 $(3, 1)$ 向北走两格到 $(1, 1)$。

从 $(1, 1)$ 向东走两格到 $(1, 3)$。

从 $(1, 3)$ 向东走一格到 $(1, 4)$。

从 $(1, 4)$ 向南走两格到 $(3, 4)$。

标签: AtCoder|abc170F

来源

AtCoder|abc170F