Processing math: 100%

Задача B. Balorant

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Антона позвали на работу тестировщиком карт для одной популярной игры "Балорант". Антон уже давно играет в Балорант и знает всех персонажей. Тестировать карты он собирается на Даон - самом быстром персонаже в игре. Карта представляет собой клетчатое поле nm, каждая клетка которого или свободна, или занята препятствием. Даон может передвигаться со скоростью до k клеток в секунду. Каждую секунду Антон может выбрать, в какую сторону будет бежать Даон (вверх, вниз, влево или вправо), после чего персонаж пробегает в этом направлении от 1 до k клеток. Разумеется, что Даон может передвигаться только по свободным клеткам карты.

Работа Антона заключается в проверке, сможет ли персонаж добраться из клетки с координатами (x1,y1) в клетку (x2,y2).

Антон очень ленивый и не собирается долго работать. Всё, что он хочет - сам поиграть в Балорант. Помогите Антону написать программу, которая будет определять, за какое минимальное количество секунд Даон сможет добежать из квадрата (x1,y1) в квадрат (x2,y2). Если геймдизайнеры продумали уровень плохо, и персонаж никак не может добраться до требуемой точки - программа должна вывести 1

Формат входных данных

В первой строке подаются целые числа n,m,k(1n,m,k1000) - размеры карты и скорость Даон.

Во второй строке содержатся 4 целых числа x1,y1,x2,y2(1x1,x2n,1y1,y2m). В задаче гарантируется, что клетки (x1,y1) и (x2,y2) свободны.

Далее следует n строк, каждая длиной m символов. Каждая i-ая строка содержит на j-ой позиции символ "." для свободной клетки или символ "#", если клетка занята препятствием.

Формат выходных данных

Выведите одно единственное число - минимальное время, за которое Даон добежит из клетки (x1,y1) в клетку (x2,y2). Если Даон не может добраться из (x1,y1) в (x2,y2) - выведите 1.

Ограничения

(1n,m,k1000)

(1x1,x2n,1y1,y2m)

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
nmk
1101n101m101k10
2351n1001m1001k100
3551n10001m10001k1000

Пояснение к примерам

В первом примере Даон пробегает 3 клетки вправо, 2 клетки вниз и 3 клетки вправо. Ответ 3 секунды. Иллюстрация движения Даон в первом примере:

Д-→Д

###↓

Д←-Д

Во втором примере Даон не смогла дойти до требуемой точки, поэтому ответ -1

Примеры тестов

Стандартный вход Стандартный выход
1
3 4 4
1 1 3 1
....
###.
....
3
2
2 2 1
1 1 2 2
.#
#.
-1

0.096s 0.011s 13