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’ объединяют участки в один.
N = 30;
var
a: array [1..N] of integer;
i, nel, x: integer;
begin
writeln('Введите элементы массива');
for i := 1 to N do read(a[i]);
writeln('введите Х');
readln(x);
nel := 0; // номер найденного элемента
i := 1;
while (i <= n) and (nel = 0) do
begin
if a[i] = x then nel := i;
i := i + 1
end;
if nel > 0 then
writeln('Номер элемента ', nel)
else
writeln('Не найден элемент, удовлетворяющий условию')
end.
Тестовый пример:
Введите элементы массива
1 3 6 8 4 9 14 -4 7 45 4 8 0 23 63 253 23 453 54 20 54 12 -56 3 0 -34 28 27 90 23
введите Х
0
Номер элемента 13
begin
if pos('7', IntToStr(x)) = 0
then result := False
else result := True
end;
const
n = 1000;
var
a: array[1..n] of integer;
ii: integer;
i, o: text;
begin
AssignFile(i, 'Input.dat');
AssignFile(o, 'Output.dat');
Rewrite(o);
Reset(i);
for ii := 1 to n do
readln(i, a[ii]);
for ii := 1 to n do
if find(a[ii])
then writeln(o, a[ii]);
CloseFile(i);
CloseFile(o);
end.
Функция Find пытается разыскать цифру 7 в целом числе, которое она получает в качестве аргумента. Если поиск успешен, возвращается "Истинно", если нет - "Ложно" - это символизирует успешность поиска.
В программе используются два текстовых файла - i, связанный с файлом input.dat, и o, связанный с файлом Output.dat.
Данные из input.dat считываются в целочисленный массив a, содержащий 1000 элементов.
Затем элементы массива просматриваются, начиная с первого, на предмет наличия в элементе числа, содержащего цифру 7, что проверяется вызовом функции Find. Каждое число, содержащее цифру 7, выводится в файл Output.dat.
Недостаток программы: если в файле input.dat будет меньше 1000 чисел, программа все равно будет просматривать все 1000 элементов, анализируя оставшийся "мусор". так же есть большая вероятность, что программа будет аварийно завершена, если этот "мусор" не сможет быть интерпретирован, как целые числа.