|
Вирусы - 2
(Время: 1 сек. Память: 16 Мб Сложность: 40%)
Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. Некоторые клетки обладают иммунитетом, заразить их невозможно и через них не распространяются вирусы. Напишите программу, которая найдёт минимально возможное число вирусов, с помощью которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток).
Входные данные
В первой строке входного файла INPUT.TXT содержится два натуральных числа n и m - размеры таблицы (количество строк и столбцов соответственно). Известно, что 1 ≤ n, m ≤ 100. Во второй строке вначале записано одно число k – количество защищённых клеток, а далее записаны 2k чисел – координаты этих клеток yi, xi (0 ≤ k ≤ n×m, 1 ≤ yi ≤ n, 1 ≤ xi ≤ m).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимально возможное число вирусов.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 5
3 1 3 2 1 2 2 | 2 |
Пояснения
В приведённом примере таблица имеет размер 4*5, в ней символом «I» помечены защищённые клетки. Видно, что двух вирусов достаточно для заражения всей области. Их можно поместить, например, в клетки, помеченные символом «V».
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
