Задача №115302. Побег слайма
Никите на день рождения подарили набор для создания слаймов. Обрадовавшись подарку, Никита сделал квадратного слайма, и положил его на стол. Слайм, испугавшись предстоящих экспериментов Никиты, решил от него сбежать.
Стол представляет собой прямоугольное поле из \(n\) строк и \(m\) столбцов. В некоторых клетках стола находятся дырки, если хотя бы одна клетка слайма окажется на дырке, он упадет со стола. Слайм занимает 4 клетки, и изначально находится в верхнем левом углу поля размером \(2 \times 2\), цель его побега — занять нижний правый угол размером \(2 \times 2\).
Слайм может передвигаться по полю с помощью трансформаций . Трансформация заключается в следующем: одна из клеток слайма передвигается в другую, соседнюю с ней по стороне или углу. После трансформации слайм должен образовывать 4-связную фигуру (иными словами, между любыми двумя клетками слайма должен существовать путь по клеткам слайма, переходящий каждый раз в клетку, соседнюю по стороне).
Слайм хочет сбежать от Никиты как можно быстрее, чтобы его клетки никогда не оказывались на клетках стола с дырками. Найдите минимальное число трансформаций, за которое он сможет это сделать.
Первая строка содержит два целых числа \(n\) и \(m\) (\(2 \le n, m \le 3 \cdot 10^5\); \(n \cdot m \le 3 \cdot 10^5\)) — размеры стола.
В следующих \(n\) строках содержатся по \(m\) символов \(a_{i, j}\) — описание стола. Символ « # » обозначает дырку в столе, а символ « . » обозначает поверхность стола.
Гарантируется, что верхний левый и нижний правый углы стола размером \(2 \times 2\) составляют поверхность стола.
Выведите минимальное количество трансформаций, в результате которых слайм займет нижний правый угол стола размером \(2 \times 2\), начав в верхнем левом, либо \(-1\), если он не сможет этого сделать.
На рисунке приведены трансформации для первого примера. Черным обозначены дырки в столе, серым — клетки слайма. Стрелками обозначены передвижения клеток.

3 3 ..# ... #..
5
3 5 ..### ..... ##...
-1