Автор: | Денис Лысенко | Ограничение времени: | 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 |
|
|