3. Радиолюбитель Ограничение времени 1 секунда
Ограничение памяти 244Mb
Ввод grass.in
Вывод grass.out
Джон решил заняться радиолюбительством, прочитал в сети Интернет о технологии ЛУТ (лазерно-утюжная технология) и решил попробовать. Суть технологии упрощённо состоит в следующем: сначала на лазерном принтере печатают маску (схему проводников), которую накладывают на заготовку платы, покрытую медью, и травят кислотным раствором. В результате, медь растворяется там, где нет маски (т.е. чернил).

Однако, принтер у Джона очень старый, в результате чего некоторые дорожки перетравились и оказались разорванными. Он решил их дорисовать дорогим контактным клеем "Контактол". Естественно, он хочет потратить как можно меньше этого клея.

Джон раньше занимался математикой, поэтому быстро формализовал и упростил задачу. Во-первых, каждый раз достаточно рассматривать только два целых участка повреждённого проводника. Во-вторых, если для соединения каждой пары таких участков потратить минимум клея, то минимум клея уйдёт и на весь проводник.

Осталось дело за малым - научиться оптимально соединять два участка проводника. Участок платы представлен массивом символов NM, например, так:

Здесь каждый символ '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’ объединяют участки в один.

280

399

Посмотреть ответы 1

Ответы на вопрос:

mila336

Информатика

4,6(75 оценок)

1). 1 мбит = 1024 кбит = 1024*1024 бит = 1024*1024/8 байт = 131072 байт (под условия ответа подходит, т.к. 131072 это 2 в 17 степени) 2). 0,25 гбит = 1024*0,25 мбит = (1/4) * 1024 = 256 мбит

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Информатика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.