← 返回题目列表

Codeforces · 877/D

D. Olya 和能量饮料

中文机器翻译题面 查看原题

Olya 喜欢能量饮料。她非常喜欢它们,以至于她的房间里堆满了能量饮料的空罐。

从形式上来说,她的房间可以表示为一个由 n × m 个单元格组成的区域,每个单元格都是空的或散落着罐头。

Olya 喝了很多能量饮料,所以现在她每秒可以跑 k 米。每一秒,她都会选择四个方向(上、下、左或右)之一,并沿该方向跑 1 米到 k 米。当然,她只能穿过空荡荡的牢房。

现在 Olya 需要从单元格 (x1, y1) 到达单元格 (x2, y2)。如果她的动作达到最佳状态,需要多少秒?

保证单元格 (x1, y1) 和 (x2, y2) 为空。这些单元可以重合。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n, m, k ≤ 1000) — 房间的大小和 Olya 的速度。

接下来的 n 行每行包含 m 个字符,其中第 i 行在第 j 个位置上包含“#”,如果单元格 (i, j) 中散布着罐头,则第 i 行包含“.”。否则。

最后一行包含四个整数 x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — 第一个和最后一个单元格的坐标。

输出

打印一个整数——Olya 从 (x1, y1) 到 (x2, y2) 所需的最短时间。

如果无法从 (x1, y1) 到达 (x2, y2),则打印 -1。

示例

输入 #1

3 4 4
....
###.
....
1 1 3 1

输出 #1

3

输入 #2

3 4 1
....
###.
....
1 1 3 1

输出 #2

8

输入 #3

2 2 1
.#
#.
1 1 2 2

输出 #3

-1

注意

在第一个示例中,Olya 应在第一秒内向右跑 3 米,在第二秒内向下跑 2 米,在第三秒内向左跑 3 米。

在第二个示例中,Olya 应向右跑 3 秒,然后向下跑 2 秒,然后向左跑 3 秒。

Olya不建议喝能量饮料,并且普遍认为这不好。