Задача №112115. Колпачок
Скучая на одном из уроков, отличник Петя Пяточкин придумал себе развлечение. Он зарисовал ручкой некоторые клеточки прямоугольного листа, вырванного из тетради, снял с ручки колпачок и поставил его на одну из закрашенных клеток. Далее Петя последовательно переставляет колпачок из одной зарисованной клетки на другую зарисованную клетку, которая находится в той же строке или в том же столбце, что и предыдущая. Петя выбрал некоторую закрашенную клетку и хочет переместить туда колпачок из начальной клетки за как можно меньшее количество ходов.
Напишите программу, которая по данным о размерах листа бумаги, конфигурации закрашенных клеток, размещения колпачка и целевой клетки найдет наименьшее возможное количество передвижений, за которые Петя сможет переместить колпачок из начальной клетки в целевую, следуя придуманным им правилам.
В первой строке входного файла записано два целых числа: количество строк N и количество столбцов M клеток, из которых состоит лист, 2 ≤ M ≤ N ≤ 1000. Каждая из последующих N строк содержит по M символов:
1. x (маленькая буква латинского алфавита) — закрашенная клетка.
2. . (точка) — пустая клетка.
3. o (маленькая буква латинского алфавита) — начальная клетка.
4. + (плюс) — целевая клетка.
Во входных данных задана ровно одна начальная и ровно одна целевая клетка.
Выходной файл должен содержать единственное число — наименьшее количество перемещений колпачка, которые требуется сделать Пете для достижения цели. Если же в соответствии с заданными правилами нельзя достичь целевой клетки, то требуется вывести −1.
3 2 x+ xx o.
2
4 4 .o.x x.x. .x.x x.+.
-1