Question

«вирусы» для моделирования различных объектов часто применяются так называемые клеточные поля. в простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. в биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. некоторые клетки иммунитетом, заразить их невозможно и через них не распространяются вирусы. требуется написать программу, которая определяет минимально возможное число вирусов, с которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток). описание входных данныхв первой строке входного файла input.txt записаны два натуральных числа n и m -размеры таблицы (количество строк и столбцов соответственно). известно, что 1 n, m 100. во второй строке вначале записано одно число k – количество защищённых клеток, а далее записаны 2k чисел – координаты этих клеток xi, yi (0 k n m, 1 xi n, 1 yi m). описание выходных данных в единственную строку выходного файла output.txt нужно вывести одно число –минимально возможное число вирусов. примеры входных и выходных данных input.txt 4 5 3 1 3 2 1 2 2 output.txt 2

Answer 1

Uses GraphABC;
const types = 3;
rmax = 4;
CanEat = rmax;
eps = 0.00001;
epsustupi = 0.1;
strahkraj = 3;
ustupi = CanEat*10;
BkColor = clBlack;
Height = 600;
Width = 780;
xmin = 10;
ymin = 10;
xmax = Width - 100;
ymax = Height - 140;
Type
fishtype = class
c, CanRazm, MaxKol, Kol, MaxLife, MinFood: integer;

Speed, See: real;
constructor create(ac, aCanRazm, aMaxKol, aMaxLife, aMinFood:integer; aSpeed, aSee: real);
begin
c:= ac; CanRazm:= aCanRazm; MaxKol:= aMaxKol; Kol:= 1;
MaxLife:= aMaxLife; MinFood:= aMinFood; Speed:= aSpeed; See:= aSee
end;
procedure ShowKol(y: integer);
var s: string;
begin
SetFontColor(c);
TextOut(xmax + 20, y, ' ');
str(Kol, s);
TextOut(xmax + 20, y, s);
end;
end;
var opisanie: array[0..types] of fishtype;
Type
fish = class
x, y, r, dx0, dy0: real;
tip, life, razm, status, food: integer;

next, prev: fish;
constructor Create(ax, ay, ar: real; atip: integer; aprev, anext: fish);
begin
x:= ax; y:= ay; r:= ar; tip:= atip; prev:= aprev; next:= anext;
life:= 0; razm:= 0; dx0:= random; dy0:= random; status:= 1; food:= 0;
end;
procedure show;
begin
SetPenColor(opisanie[tip].c);
circle(round(x), round(y), round(r))
end;
procedure hide;
begin
SetPenColor(BkColor);
circle(round(x), round(y), round(r))
end;
destructor Destroy;
begin
hide;
opisanie[tip].kol:= opisanie[tip].kol - 1;
opisanie[tip].ShowKol(tip*40 + 20);
end;
procedure moveto(dx, dy: real);
begin
hide;
x:= x + dx; y:= y + dy;
if x > xmax then x:= xmax;
if x < xmin then x:= xmin;
if y > ymax then y:= ymax;
if y < ymin then y:= ymin;
show
end;
procedure MakeDeti(var mama, StartAkula, KonAkula, StartKilka, KonKilka : fish);
var d: fish;
begin
razm:= 0;
food:= 0;
d:= fish.create(x, y, r, tip, mama, next);
next.prev:= d;
next:= d;
if mama = KonAkula then KonAkula:= d;
if mama = KonKilka then KonKilka:= d;
opisanie[tip].kol:= opisanie[tip].kol + 1;
opisanie[tip].ShowKol(tip*40 + 20);
end;
procedure step(var ribka, StartAkula, KonAkula, StartKilka, KonKilka : fish);
var i, imin: integer;
dx, dy, d, dx2, dy2, dmin: real;
t, trup, found: fish;
FoundOhot: boolean;
begin
status:= 1;
dx:= 0; dy:= 0;
if tip > 0 then
begin
t:= StartAkula;
if t<>nil then
repeat
d:= sqrt((x - t.x)*(x - t.x) + (y - t.y)*(y - t.y));
if d < opisanie[tip].See then
begin
if d < eps then d:= eps;
dx2:= (x - t.x)/(d*d);
dy2:= (y - t.y)/(d*d);
dx:= dx + dx2;
dy:= dy + dy2;
status:= 2;
end;
t:= t.next
until t = KonAkula.next;
if x - xmin < opisanie[tip].See then dx:= dx + 1/((x - xmin + eps)*strahkraj);
if xmax - x < opisanie[tip].See then dx:= dx + 1/((x - xmax - eps)*strahkraj);
if y - ymin < opisanie[tip].See then dy:= dy + 1/((y - ymin + eps)*strahkraj);
if ymax - y < opisanie[tip].See then dy:= dy + 1/((y - ymax - eps)*strahkraj);
d:= sqrt(dx*dx + dy*dy);
if d < eps then
begin
dx:= 2*status*random*opisanie[tip].Speed - status*opisanie[tip].Speed;
dy:= 2*status*random*opisanie[tip].Speed - status*opisanie[tip].Speed