Задача №113305. Вирусы
Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. Некоторые клетки обладают иммунитетом, заразить их невозможно и через них не распространяются вирусы.
Требуется написать программу, которая определяет минимально возможное число вирусов, с помощью которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток).
В приведённом примере таблица имеет размер \(4\times5\), в ней символом "I" помечены защищённые клетки. Видно, что двух вирусов достаточно для заражения всей области. Их можно поместить, например, в клетки, помеченные символом "V".
В первой входной строке записаны два натуральных числа \(M\) и \(N\) - размеры таблицы (количество строк и столбцов соответственно). Известно, что
\(1 \le M, N \le 100\). Во второй строке вначале записано одно число \(K\) - количество защищённых клеток, а далее записаны \(2K\) чисел – координаты этих клеток \(x_i\), \(y_i\) (\(0 \le k \le M \times N, 1 \le x_i \le M, 1 \le y_i \le N\)).
Программа должна вывести одно число – минимально возможное число вирусов.
4 5 3 1 3 2 1 2 2
2