← 返回题目

题库练习 Olya and Energy Drinks

← 上一题下一题 →

A5419 | $Olya and Energy Drinks$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Olya 喜欢能量饮料。她非常喜欢，以至于她的房间里到处都是喝完的饮料罐。 形式化地说，她的房间可以用一个 $n \times m$ 的网格表示，每个格子要么是空的，要么被饮料罐占据。 Olya 喝了很多能量饮料，现在她每秒可以跑 $k$ 米。每一秒她可以选择四个方向之一（上、下、左或右），然后在该方向上连续跑 $1$ 到 $k$ 米。当然，她只能经过空的格子。 现在 Olya 需要从格子 $(x_{1},y_{1})$ 跑到格子 $(x_{2},y_{2})$。如果她以最优方式移动，最少需要多少秒？ 保证 $(x_{1},y_{1})$ 和 $(x_{2},y_{2})$ 这两个格子都是空的，这两个格子可以是同一个。

输入格式

第一行包含三个整数 $n$、$m$、$k$（$1 \leq n, m, k \leq 1000$）——表示房间的大小和 Olya 的速度。 接下来 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行第 $j$ 个字符是 "\#"，表示格子 $(i, j)$ 被饮料罐占据，否则是 "."，表示格子是空的。 最后一行包含四个整数 $x_{1},y_{1},x_{2},y_{2}$（$1 \leq x_{1}, x_{2} \leq n$，$1 \leq y_{1}, y_{2} \leq m$），表示起点和终点的坐标。

输出格式

输出一个整数，表示 Olya 从 $(x_{1},y_{1})$ 到 $(x_{2},y_{2})$ 所需的最少时间（秒）。 如果无法从 $(x_{1},y_{1})$ 到达 $(x_{2},y_{2})$，输出 $-1$。

输入输出样例

输入 #1

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

输出 #1

输入 #2

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

输出 #2

输入 #3

2 2 1
.#
#.
1 1 2 2

输出 #3

-1

C++ 编辑器

输入

输出