28539번 - Стрелочник 다국어

문제

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

Ловушка представляет из себя матрицу размера $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,ドル если это невозможно.

제한

힌트