Лес
Лес
В средней полосе России иногда растет лес. Для того, чтобы отделить лес от полезных пахотных земель, между лесом и полем был построен забор. Однако лес со временем растет и забор требуется перенести.
Местность можно представить в виде карты из n × m клеток. Каждая клетка содержит в себе либо лес, либо поле, либо забор. Клетки содержащие забор обладают следующими свойствами:
- Забор связен. Это значит, что от каждой его клетки до каждой можно дойти, передвигаясь только по соседним клеткам (соседними считаются клетки, имеющие общую сторону).
- Забор минимален по включению, то есть убрав какую-либо клетку из забора (заменив её на лес или поле), он перестанет быть забором.
- Забор разделяет лес и поле, а именно все клетки слева от забора являются лесом, все клетки справа от забора являются полем.
- Забор можно представить в виде последовательности клеток таким образом, что следующая клетка находится от предыдущей слева, справа или снизу.
Вам разрешается под забор использовать все клетки, которые он занимал изначально, а также клетки, находящиеся не более чем на один справа от исходных клеток забора (запрещается использовать левый и правый столбцы карты). Вашей задачей будет построить забор минимальной длины, удовлетворяющий всем вышеприведенным условиям забора. Известно, что изначальный забор является забором, а также, что левый столбец карты целиком занят лесом, а правый столбец карты целиком занят полем.
Входные данные
В первой строке находятся два числа n и m (1 ≤ n, m ≤ 1000) - размеры карты. Далее следует n строк по m символов в каждой - карта, описывающая исходное положение леса, поля и забора. Клетки, занятые лесом, обозначаются символом "F", клетки, занятые полем - символом ".", клетки, занятые забором - символом "#".
Выходные данные
Выведите минимальную длину забора, которую можно получить.
5 4 FF#. F##. F#.. F##. FF#.
5