{"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 empty or littered with cans.\n\nOlya 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.\n\nNow 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?\n\nIt's guaranteed that cells (_x_1, _y_1) and (_x_2, _y_2) are empty. These cells can coincide.\n\n## Input\n\nThe first line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _m_, _k_ ≤ 1000) — the sizes of the room and Olya's speed.\n\nThen _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.\n\nThe 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.\n\n## Output\n\nPrint a single integer — the minimum time it will take Olya to get from (_x_1, _y_1) to (_x_2, _y_2).\n\nIf it's impossible to get from (_x_1, _y_1) to (_x_2, _y_2), print _\\-1_.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn second sample Olya should run to the right for 3 seconds, then down for 2 seconds and then to the left for 3 seconds.\n\n_Olya does not recommend drinking energy drinks and generally believes that this is bad_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Olya 爱喝能量饮料。她太爱喝了，以至于她的房间里到处都是空的能源饮料罐。\n\n形式上，她的房间可以表示为一个 $n × m$ 的网格，每个格子要么是空的，要么被饮料罐占据。\n\nOlya 喝了太多能量饮料，现在她每秒可以跑 $k$ 米。每秒她选择四个方向之一（上、下、左或右），并沿该方向跑 $1$ 到 $k$ 米的距离。当然，她只能通过空的格子。\n\n现在 Olya 需要从格子 $(x1, y1)$ 移动到格子 $(x2, y2)$。如果她以最优方式移动，需要多少秒？\n\n保证格子 $(x1, y1)$ 和 $(x2, y2)$ 是空的。这两个格子可能重合。\n\n第一行包含三个整数 $n$, $m$ 和 $k$ ($1 ≤ n, m, k ≤ 1000$) —— 房间的尺寸和 Olya 的速度。\n\n接下来 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行的第 $j$ 个字符为 \"#\" 表示格子 $(i, j)$ 被饮料罐占据，为 \".\" 表示该格子为空。\n\n最后一行包含四个整数 $x1, y1, x2, y2$ ($1 ≤ x1, x2 ≤ n$, $1 ≤ y1, y2 ≤ m$) —— 起点和终点的坐标。\n\n请输出一个整数 —— Olya 从 $(x1, y1)$ 到 $(x2, y2)$ 所需的最少时间。\n\n如果无法从 $(x1, y1)$ 到达 $(x2, y2)$，请输出 $-1$。\n\n在第一个样例中，Olya 应在第一秒向右跑 $3$ 米，第二秒向下跑 $2$ 米，第三秒向左跑 $3$ 米。\n\n在第二个样例中，Olya 应向右跑 $3$ 秒，然后向下跑 $2$ 秒，再向左跑 $3$ 秒。\n\n_Olya 不建议饮用能量饮料，通常认为这很不好_。\n\n## Input\n\n第一行包含三个整数 $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$) —— 起点和终点的坐标。\n\n## Output\n\n请输出一个整数 —— Olya 从 $(x1, y1)$ 到 $(x2, y2)$ 所需的最少时间。如果无法从 $(x1, y1)$ 到达 $(x2, y2)$，请输出 $-1$。\n\n[samples]\n\n## Note\n\n在第一个样例中，Olya 应在第一秒向右跑 $3$ 米，第二秒向下跑 $2$ 米，第三秒向左跑 $3$ 米。在第二个样例中，Olya 应向右跑 $3$ 秒，然后向下跑 $2$ 秒，再向左跑 $3$ 秒。_Olya 不建议饮用能量饮料，通常认为这很不好_.","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 \\le n, 1 \\le j \\le m \\} $,  \n- A cell $ (i,j) $ is *walkable* if it contains `'.'`, blocked if it contains `'#'`.  \nLet $ s = (x_1, y_1) $, $ t = (x_2, y_2) \\in V $ be the start and target positions, both walkable.  \n\n**Constraints**  \n1. $ 1 \\le n, m, k \\le 1000 $  \n2. For all $ (i,j) \\in V $:  \n   - $ (i,j) $ is walkable iff the input character at row $ i $, column $ j $ is `'.'`  \n3. Olya moves in one of four cardinal directions per second.  \n4. In one second, she can move $ 1 $ to $ k $ cells in a single direction, but only through walkable cells.  \n5. Movement cannot pass through blocked cells or leave the grid.  \n\n**Objective**  \nFind the minimum number of seconds required to move from $ s $ to $ t $.  \nIf unreachable, return $ -1 $.  \n\nFormally, compute:  \n$$\n\\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\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF877D","tags":["data structures","dfs and similar","graphs","shortest paths"],"sample_group":[["3 4 4\n....\n###.\n....\n1 1 3 1","3"],["3 4 1\n....\n###.\n....\n1 1 3 1","8"],["2 2 1\n.#\n#.\n1 1 2 2","\\-1"]],"created_at":"2026-03-03 11:00:39"}}