Məsələlər
Колпачок
Колпачок
Скучая на одном из уроков, отличник Петя Пяточкин придумал себе развлечение. Он зарисовал ручкой некоторые клеточки прямоугольного листа, вырванного из тетради, снял с ручки колпачок и поставил его на одну из закрашенных клеток. Далее Петя последовательно переставляет колпачок из одной зарисованной клетки на другую зарисованную клетку, которая находится в той же строке или в том же столбце, что и предыдущая. Петя выбрал некоторую закрашенную клетку и хочет переместить туда колпачок из начальной клетки за как можно меньшее количество ходов.
Напишите программу, которая по данным о размерах листа бумаги, конфигурации закрашенных клеток, размещения колпачка и целевой клетки найдет наименьшее возможное количество передвижений, за которые Петя сможет переместить колпачок из начальной клетки в целевую, следуя придуманным им правилам.
\InputFile
В первой строке записано два целых числа: количество строк \textbf{N }и количество столбцов \textbf{M }клеток (\textbf{2 }≤ \textbf{M }≤ \textbf{N }≤ \textbf{1000}), из которых состоит лист. Каждая из последующих \textbf{N} строк содержит по \textbf{M} символов:
\begin{enumerate}
\item \textbf{x} (маленькая буква латинского алфавита) - закрашенная клетка.
\item \textbf{.} (точка) - пустая клетка.
\item \textbf{o} (маленькая буква латинского алфавита) - начальная клетка.
\item \textbf{+} (плюс) - целевая клетка.
\end{enumerate}
Во входных данных задана ровно одна начальная и ровно одна целевая клетка.
\OutputFile
Вывести одно число - наименьшее количество перемещений колпачка, которые требуется сделать Пете для достижения цели. Если же в соответствии с заданными правилами нельзя достичь целевой клетки, то требуется вывести -\textbf{1}.
Giriş verilənləri #1
3 2 x+ xx o.
Çıxış verilənləri #1
2