Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Антона позвали на работу тестировщиком карт для одной популярной игры "Балорант". Антон уже давно играет в Балорант и знает всех персонажей. Тестировать карты он собирается на Даон - самом быстром персонаже в игре. Карта представляет собой клетчатое поле n * m, каждая клетка которого или свободна, или занята препятствием. Даон может передвигаться со скоростью до k клеток в секунду. Каждую секунду Антон может выбрать, в какую сторону будет бежать Даон (вверх, вниз, влево или вправо), после чего персонаж пробегает в этом направлении от 1 до k клеток. Разумеется, что Даон может передвигаться только по свободным клеткам карты.
Работа Антона заключается в проверке, сможет ли персонаж добраться из клетки с координатами (x1, y1) в клетку (x2, y2).
Антон очень ленивый и не собирается долго работать. Всё, что он хочет - сам поиграть в Балорант. Помогите Антону написать программу, которая будет определять, за какое минимальное количество секунд Даон сможет добежать из квадрата (x1, y1) в квадрат (x2, y2). Если геймдизайнеры продумали уровень плохо, и персонаж никак не может добраться до требуемой точки - программа должна вывести − 1
В первой строке подаются целые числа n, m, k(1 ≤ n,m,k ≤ 1000) - размеры карты и скорость Даон.
Во второй строке содержатся 4 целых числа x1, y1, x2, y2(1 ≤ x1,x2 ≤ n, 1 ≤ y1,y2≤m). В задаче гарантируется, что клетки (x1, y1) и (x2, y2) свободны.
Далее следует n строк, каждая длиной m символов. Каждая i-ая строка содержит на j-ой позиции символ "." для свободной клетки или символ "#", если клетка занята препятствием.
Выведите одно единственное число - минимальное время, за которое Даон добежит из клетки (x1, y1) в клетку (x2, y2). Если Даон не может добраться из (x1, y1) в (x2, y2) - выведите − 1.
(1 ≤ n,m,k ≤ 1000)
(1 ≤ x1,x2 ≤ n, 1 ≤ y1,y2≤m)
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | ||
---|---|---|---|---|
n | m | k | ||
1 | 10 | 1 ≤ n ≤ 10 | 1 ≤ m ≤ 10 | 1 ≤ k ≤ 10 |
2 | 35 | 1 ≤ n ≤ 100 | 1 ≤ m ≤ 100 | 1 ≤ k ≤ 100 |
3 | 55 | 1 ≤ n ≤ 1000 | 1 ≤ m ≤ 1000 | 1 ≤ k ≤ 1000 |
В первом примере Даон пробегает 3 клетки вправо, 2 клетки вниз и 3 клетки вправо. Ответ 3 секунды. Иллюстрация движения Даон в первом примере:
Д-→Д
###↓
Д←-Д
Во втором примере Даон не смогла дойти до требуемой точки, поэтому ответ -1
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|