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

210

374

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

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

Polina212

Информатика

4,5(71 оценок)

1) program n1; var a,b,c: real; sum: integer; begin readln(a,b,c); sum: =trunc(a+b+c); writeln(sum); end. 2) program n2; var a,n: integer; x: real; begin readln(a,n); x: =frac(a/n); writeln(x) end. 3) program n3; var a,b,c,d: real; sum: integer; begin readln(a,b,c,d); sum: =round(a+b+c+d); writeln(sum); end.