CF877D Olya and Energy Drinks

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$。

在第一个样例中，Olya 第一秒向右跑 $3$ 米，第二秒向下跑 $2$ 米，第三秒向左跑 $3$ 米。 在第二个样例中，Olya 需要向右跑 $3$ 秒，然后向下跑 $2$ 秒，再向左跑 $3$ 秒。 Olya 不推荐大家喝能量饮料，并且认为这其实并不好。 由 ChatGPT 5 翻译