Ковпачок#4977
Під час уроку найкращий учень, Петро П'яточкін, вигадав гру, щоб розважитись. Він узяв прямокутний аркуш зі свого зошита і закрасив ручкою деякі клітинки. Потім відкрив ковпачок ручки і поставив його на одну із закрашених клітинок. Після цього Петро почав пересувати ковпачок з однієї закрашеної клітинки на іншу так, щоб кожен хід був у тому самому рядку або стовпці, що й попередній. Зараз Петро обрав конкретну закрашену клітинку за мету й хоче дістатися до неї з початкової позиції ковпачка за мінімальну кількість ходів.
Ваша задача — написати програму, яка за заданими розмірами аркуша, розташуванням закрашених клітинок, початковою позицією ковпачка та цільовою клітинкою визначає мінімальну кількість ходів, необхідних Петрові, щоб дістатися цілі за його правилами.
Перший рядок містить два цілі числа: кількість рядків та кількість стовпців аркуша (2 \leq M \leq N \leq 1000).
Далі йде рядків по символів, які описують клітинки:
x (мала латинська літера) — закрашена клітинка.
. (крапка) — порожня клітинка.
o (мала латинська літера) — початкова клітинка, де стоїть ковпачок.
+ (плюс) — цільова клітинка.
Гарантується, що у вхідних даних є рівно одна початкова і одна цільова клітинка.
Виведіть одне ціле число — мінімальну кількість ходів, необхідних Петрові, щоб дістатися до цільової клітинки. Якщо це неможливо за заданими правилами, виведіть -1.
Приклад 1