Условие:
Царь Леонид ездит на тракторе по прямоугольному клетчатому полю размером H × W. Трактор у Леонида модели «только вперёд» и не имеет руля. Когда трактор всё-таки нужно повернуть, то на помощь Леониду приходят спартанцы — они поднимают трактор и поворачивают его в одном из 8 направлений (по вертикали, горизонтали или двум диагоналям).
Местостность в окрестностях Спарты каменистая и некоторые клетки непроходимы даже на тракторе. Царь Леонид хочет торжественно проехать из одной точки поля в другую, сделав при этом наименьшее количество поворотов (силы спартанцев надо беречь для боя с Ксерксом). Изначально трактор лежит в начальной точке вверх колесами, чтобы его направить куда-либо нужно привлечь спартанцев. Направление трактора в конечной точке не имеет значения.
Формат ввода
В первой строке входного файла заданы целые числа H, W (1 ≤ H, W ≤ 1000) — высота и ширина поля.
В последующих H строках задано поле, блокированные клетки обозначены латинскими буквами "X", а свободные — точками.
После поля следует строка с двумя целыми числами sx, sy (1 ≤ sx ≤ W, 1 ≤ sy ≤ H) — координаты стартового положения трактора.
Последней строкой идут два целых числа tx, ty (1 ≤ tx ≤ W, 1 ≤ ty ≤ H) — координаты конечного положения трактора.
Координаты отсчитываются от нижнего левого угла поля. Стартовое положение не совпадает с конечным. Стартовая и конечная клетки не являются заблокированными.
Формат вывода
Если пути не существует — выведите одно число -1. Иначе выведите единственное натуральное число — минимальное количество поворотов, которые спартанцы должны будут сделать по пути к конечной клетке.
Код должен использовать bfs. Изначальный поворот (в начале движения из стартовой точки) не учитывается. Пример теста:
Ввод:
5 7
XX....X
X.XXX..
..XXX.X
X.X...X
....XXX
1 1
6 5
Вывод: 3.