ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1145. Нить в лабиринте

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Лабиринт в виде прямоугольника размером m × n поделен на квадратные ячейки размером 1 × 1 прямыми, параллельными сторонам лабиринта. Каждая ячейка лабиринта или свободна, или непроходима. Можно перемещаться между свободными ячейками лабиринта, имеющими общую сторону. При этом нельзя выходить за границы лабиринта. Лабиринт устроен специальным образом: для любых двух свободных ячеек существует единственный путь из одной в другую.
Где-то в лабиринте есть две специальные ячейки, в центре каждой из которых расположен крюк. Если вы привяжете нить к крюкам в этих ячейках, автоматически откроется секретная дверь. Ваша задача — зная схему лабиринта, приготовить нить как можно меньшей длины, которой гарантированно хватит для соединения двух специальных ячеек, где бы они ни находились.

Исходные данные

В первой строке записаны целые числа n и m (3 ≤ n, m ≤ 820). В следующих m строках описана схема лабиринта. Каждая из них содержит n символов. Каждый символ — это или "#" (обозначает непроходимую ячейку), или "." (обозначает свободную ячейку). В лабиринте не менее двух свободных ячеек.

Результат

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

Пример

исходные данныерезультат
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
8