F - 河虫

得分：$600$ 分

问题描述

一个水黾 Snuke 生活在一片可以看作是一个 $H$ 行 $W$ 列的方格的矩形池塘中。$(i,j)$ 表示位于北面第 $i$ 行、西面第 $j$ 列的方格。

有些方格上有莲叶，无法进入。 方格 $(i,j)$ 上有莲叶当且仅当 $c_{ij}$ 是 @，没有莲叶当且仅当 $c_{ij}$ 是 .。

Snuke 可以一次移动 $1$ 到 $K$ 个方格（包括两端）向上下左右四个方向之一移动。 无法穿过有莲叶的方格，禁止移动到池塘之外。

找到 Snuke 从方格 $(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}$

输出

输出 Snuke 从方格 $(x_1,y_1)$ 移动到方格 $(x_2,y_2)$ 所需的最小步数，如果无法到达则输出 -1。

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

5

最初，Snuke 位于方格 $(3,2)$。 最少需要 5 步到达方格 $(3,4)$：

• 从 $(3,2)$ 往西走一步到达 $(3,1)$。

• 从 $(3,1)$ 往北走两步到达 $(1,1)$。

• 从 $(1,1)$ 往东走两步到达 $(1,3)$。

• 从 $(1,3)$ 往东走一步到达 $(1,4)$。

• 从 $(1,4)$ 往南走两步到达 $(3,4)$。

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

2

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

-1