Рабочее место участника

Королевство Флатландия имеет форму прямоугольника размером `N`x`M` клеток. Для защиты Флатландия в нескольких клетках были построены крепости, в которых размещены войска. При нападении войско из крепостей пешим маршем отправляется к месту появления врага. Войско может переходить только в соседнюю клетку, имеющую общую границу с клеткой, где находится войско. Такой переход выполняется за 1 единицу времени. Некоторые клетки Флатландии, в которых находятся леса и озера, горы и равнины, являются непроходимыми для войск. Король хочет выяснить за какое минимальное время войска могут гарантированно добраться до остальных клеток страны.

Напишите программу, которая вычисляет это время для заданной карты Флатландии.

Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N\ ≤\ 200`, `1\ ≤\ M\ ≤\ 200`) – размеры Флатландии. Далее следует `N` строк, содержащих по `M` символов '#' (непроходимая для войск клетка), '.' (удобная для передвижения войск клетка) и '*' (клетка с крепостью). Гарантируется, что войска могут добраться до всех клеток, обозначенных символом '.', из какой-либо крепости.

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

4 4
*#..
...*
.##.
...#

5