Цивилизация

Карта мира в компьютерной игре «Цивилизация» версии 1.0 представляет собой прямоугольник, разбитый на квадратики. Каждый квадратик может иметь один из нескольких возможных рельефов, для простоты ограничимся тремя видами рельефов – поле, лес и вода. Поселенец перемещается по карте, при этом на перемещение в клетку, занятую полем, необходима одна единица времени, на перемещение в лес – две единицы времени, а перемещаться в клетку с водой нельзя.

У вас есть один поселенец, вы определили место, где нужно построить город, чтобы как можно скорее завладеть всем миром. Найдите минимально возможное время, за которое переселенец сможет добраться до места строительства города. На каждом ходе поселенец может перемещаться в клетку, имеющую общую сторону с той клеткой, где он сейчас находится.

Входные данные

Во входном файле INPUT.TXT записаны два натуральных числа N и M, не превосходящие 1000 – размеры карты мира (N - число строк в карте, M – число столбцов). Затем заданы координаты начального положения поселенца y и x, где y – номер строки, x – номер столбца на карте (1 ≤ y ≤ N, 1 ≤ x ≤ M), строки нумеруются сверху вниз, столбцы – слева направо. Затем аналогично задаются координаты клетки, куда необходимо привести поселенца.

Далее идет описание карты мира в виде N строк, каждая из которых содержит M символов. Каждый символ может быть либо «.» (точка), обозначающим поле, либо «W», обозначающим лес, либо «#», обозначающим воду. Гарантируется, что начальная и конечная клетки пути поселенца не являются водой.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество единиц времени, необходимое для перемещения поселенца. Если дойти из начальной клетки в конечную невозможно, выведите число -1.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]