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’ объединяют участки в один.