3. Радиолюбитель Ограничение времени 1 секунда
Ограничение памяти 244Mb
Ввод grass.in
Вывод grass.out
Джон решил заняться радиолюбительством, прочитал в сети Интернет о технологии ЛУТ (лазерно-утюжная технология) и решил попробовать. Суть технологии упрощённо состоит в следующем: сначала на лазерном принтере печатают маску (схему проводников), которую накладывают на заготовку платы, покрытую медью, и травят кислотным раствором. В результате, медь растворяется там, где нет маски (т.е. чернил).
Однако, принтер у Джона очень старый, в результате чего некоторые дорожки перетравились и оказались разорванными. Он решил их дорисовать дорогим контактным клеем "Контактол". Естественно, он хочет потратить как можно меньше этого клея.
Джон раньше занимался математикой, поэтому быстро формализовал и упростил задачу. Во-первых, каждый раз достаточно рассматривать только два целых участка повреждённого проводника. Во-вторых, если для соединения каждой пары таких участков потратить минимум клея, то минимум клея уйдёт и на весь проводник.
Осталось дело за малым - научиться оптимально соединять два участка проводника. Участок платы представлен массивом символов N*M, например, так:
Здесь каждый символ 'X' обозначает сохранившийся участок проводника, на котором медь осталась. Два символа 'X' принадлежат одному и тому же участку, если они вертикально или горизонтально соседние (диагонально соседние таковыми не считаются). Гарантируется, что в выбранном участке имеется только два участка проводника.
Джон хочет использовать как можно меньше клея, чтобы объединить два участка проводника в один. В примере выше, он может сделать это, закрасив только три дополнительных клетки (они помечены символами ‘*’ на рисунке ниже).
Джону определить минимальное количество клеток, которые нужно закрасить, чтобы объединить два участка в один.
Формат ввода
Строка 1: Два разделенных пробелом целых числа, N и M (1 ≤ N, M ≤ 50).
Строки 2..1+N: Каждая строка содержит строку из M символов 'X' и '.', указывающих состояние проводника.
Формат вывода
В единственной строке требуется вывести минимальное количество новых символов 'X', которые необходимо добавить.
Пример
Ввод Вывод
6 16
..XXX...
...XX...
.XXX..
...
XXX
3
Примечания
На рис. участки проводника показаны цифрами 1 и 2:
Три дополнительных символа ‘X’ объединяют участки в один.
