407372: GYM102775 H Пешка туда-сюда

Для олимпиады по программированию жюри попросило инопланетянина Нибо составить задачу. Нибо очень обрадовался и решил придумать самую сложную задачу. Сначала он придумал задачу, в которой из одной клетки шахматной доски нужно пройти в другую клетку конём. Но великого Нибо огорчили, сказав, что такую задачу уже давно придумали. Инопланетянин не сдался и придумал новую задачу. Теперь в его задаче были конь и пешка туда-сюда, а шахматная доска превратилась в шаманскую. Шаманская доска состоит из N × N клеток. В шаманской доске есть три вида клеток: клетки, в которых фигура превращается в коня, клетки, в которых фигура превращается в пешку туда-сюда, и клетки, в которые нельзя ходить. Задаются координаты начальной клетки и конечной клетки. Необходимо за минимальное количество ходов пройти из начальной клетки в конечную. Гарантируется, что начальная и конечная клетки не являются клетками, в которые нельзя ходить. На рисунке изображено, как ходят конь и пешка туда-сюда.

В первой строке записано число N (1 ≤ N ≤ 100) — размеры доски. В следующих N строках записано по N символов – сама доска.

Клетки доски делятся на 3 типа:

• «h» — фигура превращается в коня.
• «p» — фигура превращается в пешку туда-сюда.
• «x» — в эту клетку ходить нельзя.

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

В единственной строке выведите число – минимальное количество шагов для достижения цели. Если добраться до конечной клетки нельзя, то выведите «–1» без кавычек.

3
phx
pxx
hhh
2 1
3 3

3