410623: GYM104066 F Стрелочник

F. Стрелочникограничение по времени на тест3 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Загулявшись поздно Хэллоуинской ночью, вы и сами не заметили, как попали в ловушку к демону-стрелочнику. Было бы здорово выбраться из нее до рассвета, а иначе у вас будут все шансы остаться в ней навсегда (ну или как минимум до следующего Хэллоуина).

Ловушка представляет из себя матрицу размера $$$n \times m$$$. Некоторые клетки матрицы пусты, а в некоторых нарисованы стрелочки в соседние по стороне или углу клетки. Каждую секунду все стрелочки поворачиваются на $$$45^\circ$$$ градусов по часовой стрелке.

Обозначим направление вверх как $$$0$$$, вправо-вверх как $$$1$$$ и так далее, пустую клетку обозначим точкой. Вы находитесь в клетке с координатами $$$(a_x, a_y)$$$, и,

• находясь в пустой клетке, можете либо секунду подождать в ней, либо за секунду переместиться в соседнюю по стороне клетку;
• попадая на клетку со стрелочкой, вы моментально (за $$$0$$$ секунд) переноситесь туда, куда она указывает.

Когда вы переходите на клетку со стрелкой, она уже успевает повернуться за ту секунду, что вы шагали. Ваша задача — выбраться из ловушки как можно скорее. Попадите из стартовой точки $$$(a_x, a_y)$$$ в конечную $$$(b_x, b_y)$$$ за минимальное количество секунд, либо определите, что это невозможно, и смиритесь с тем, что вам не выбраться.

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

В первой строке через пробел даны два целых числа $$$n$$$ и $$$m$$$ — размеры ловушки ($$$1 \leqslant n, m \leqslant 1000$$$).

Во второй строке даны два целых числа $$$a_x$$$ и $$$a_y$$$ — координаты стартовой клетки ($$$1 \leqslant a_x \leqslant n$$$; $$$1 \leqslant a_y \leqslant m$$$).

В третьей строке так же даны два целых числа $$$b_x$$$ и $$$b_y$$$ — координаты конечной клетки ($$$1 \leqslant b_x \leqslant n$$$, $$$1 \leqslant b_y \leqslant m$$$).

Далее следуют $$$n$$$ строк по $$$m$$$ символов — описание матрицы. Гарантируется, что ни в стартовой, ни в конечной точке нет стрелочек.

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

В качестве ответа выведите минимальное время, необходимое, чтобы добраться из $$$(a_x, a_y)$$$ в $$$(b_x, b_y)$$$, либо $$$-1$$$, если это невозможно.

ПримерыВходные данные

2 2
1 1
2 2
.4
2.

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

8

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

1 5
1 1
1 5
.007.

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

-1

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

3 3
1 1
3 3
.05
655
01.

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

-1

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

3 3
1 1
3 3
.12
345
67.

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

7