English · Original
Chinese · Translation
Formal · Original
Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks.
Formally, her room can be represented as a field of _n_ × _m_ cells, each cell of which is empty or littered with cans.
Olya drank a lot of energy drink, so now she can run _k_ meters per second. Each second she chooses one of the four directions (up, down, left or right) and runs from 1 to _k_ meters in this direction. Of course, she can only run through empty cells.
Now Olya needs to get from cell (_x_1, _y_1) to cell (_x_2, _y_2). How many seconds will it take her if she moves optimally?
It's guaranteed that cells (_x_1, _y_1) and (_x_2, _y_2) are empty. These cells can coincide.
## Input
The first line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _m_, _k_ ≤ 1000) — the sizes of the room and Olya's speed.
Then _n_ lines follow containing _m_ characters each, the _i_\-th of them contains on _j_\-th position "_#_", if the cell (_i_, _j_) is littered with cans, and "_._" otherwise.
The last line contains four integers _x_1, _y_1, _x_2, _y_2 (1 ≤ _x_1, _x_2 ≤ _n_, 1 ≤ _y_1, _y_2 ≤ _m_) — the coordinates of the first and the last cells.
## Output
Print a single integer — the minimum time it will take Olya to get from (_x_1, _y_1) to (_x_2, _y_2).
If it's impossible to get from (_x_1, _y_1) to (_x_2, _y_2), print _\-1_.
[samples]
## Note
In the first sample Olya should run 3 meters to the right in the first second, 2 meters down in the second second and 3 meters to the left in the third second.
In second sample Olya should run to the right for 3 seconds, then down for 2 seconds and then to the left for 3 seconds.
_Olya does not recommend drinking energy drinks and generally believes that this is bad_.
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)$ 被饮料罐占据，为 "." 表示该格子为空。
最后一行包含四个整数 $x1, y1, x2, y2$ ($1 ≤ x1, x2 ≤ n$, $1 ≤ y1, y2 ≤ m$) —— 起点和终点的坐标。
请输出一个整数 —— Olya 从 $(x1, y1)$ 到 $(x2, y2)$ 所需的最少时间。
如果无法从 $(x1, y1)$ 到达 $(x2, y2)$，请输出 $-1$。
在第一个样例中，Olya 应在第一秒向右跑 $3$ 米，第二秒向下跑 $2$ 米，第三秒向左跑 $3$ 米。
在第二个样例中，Olya 应向右跑 $3$ 秒，然后向下跑 $2$ 秒，再向左跑 $3$ 秒。
_Olya 不建议饮用能量饮料，通常认为这很不好_。
## Input
第一行包含三个整数 $n$, $m$ 和 $k$ ($1 ≤ n, m, k ≤ 1000$) —— 房间的尺寸和 Olya 的速度。接下来 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行的第 $j$ 个字符为 "#" 表示格子 $(i, j)$ 被饮料罐占据，为 "." 表示该格子为空。最后一行包含四个整数 $x1, y1, x2, y2$ ($1 ≤ x1, x2 ≤ n$, $1 ≤ y1, y2 ≤ m$) —— 起点和终点的坐标。
## Output
请输出一个整数 —— Olya 从 $(x1, y1)$ 到 $(x2, y2)$ 所需的最少时间。如果无法从 $(x1, y1)$ 到达 $(x2, y2)$，请输出 $-1$。
[samples]
## Note
在第一个样例中，Olya 应在第一秒向右跑 $3$ 米，第二秒向下跑 $2$ 米，第三秒向左跑 $3$ 米。在第二个样例中，Olya 应向右跑 $3$ 秒，然后向下跑 $2$ 秒，再向左跑 $3$ 秒。_Olya 不建议饮用能量饮料，通常认为这很不好_.
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the dimensions of the grid and Olya’s maximum speed per second.
Let $ G = (V, E) $ be a grid graph where:
- $ V = \{ (i,j) \mid 1 \le i \le n, 1 \le j \le m \} $,
- A cell $ (i,j) $ is *walkable* if it contains `'.'`, blocked if it contains `'#'`.
Let $ s = (x_1, y_1) $, $ t = (x_2, y_2) \in V $ be the start and target positions, both walkable.
**Constraints**
1. $ 1 \le n, m, k \le 1000 $
2. For all $ (i,j) \in V $:
- $ (i,j) $ is walkable iff the input character at row $ i $, column $ j $ is `'.'`
3. Olya moves in one of four cardinal directions per second.
4. In one second, she can move $ 1 $ to $ k $ cells in a single direction, but only through walkable cells.
5. Movement cannot pass through blocked cells or leave the grid.
**Objective**
Find the minimum number of seconds required to move from $ s $ to $ t $.
If unreachable, return $ -1 $.
Formally, compute:
$$
\min \left\{ T \in \mathbb{Z}_{\ge 0} \mid \exists \text{ a path } s = v_0, v_1, \dots, v_T = t \text{ s.t. } \forall \ell \in \{1, \dots, T\}, \, \|v_\ell - v_{\ell-1}\|_1 \le k \text{ and all intermediate cells are walkable} \right\}
$$
API Response (JSON)
{
"problem": {
"name": "D. Olya and Energy Drinks",
"description": {
"content": "Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks. Formally, her room can be represented as a field of _n_ × _m_ cells, each cell of which is emp",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF877D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks.\n\nFormally, her room can be represented as a field of _n_ × _m_ cells, each cell of which is emp...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Olya 爱喝能量饮料。她太爱喝了，以至于她的房间里到处都是空的能源饮料罐。\n\n形式上，她的房间可以表示为一个 $n × m$ 的网格，每个格子要么是空的，要么被饮料罐占据。\n\nOlya 喝了太多能量饮料，现在她每秒可以跑 $k$ 米。每秒她选择四个方向之一（上、下、左或右），并沿该方向跑 $1$ 到 $k$ 米的距离。当然，她只能通过空的格子。\n\n现在 Olya 需要从格子 $(x1, y1)$...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, k \\in \\mathbb{Z}^+ $ denote the dimensions of the grid and Olya’s maximum speed per second. \nLet $ G = (V, E) $ be a grid graph where: \n- $ V = \\{ (i,j) \\mid 1 \\le i \\l...",
"is_translate": false,
"language": "Formal"
}
]
}