Задачка ВирусыДля моделирования различных объектов часто применяются так именуемые
Задачка Вирусы
Для моделирования различных объектов часто применяются так именуемые клеточные поля. В простом случае это прямоугольные таблицы, характеризующие некую область, а в каждой ячейке таблицы записывается какая-или информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение исполняется в соседние ячейки по вертикали и горизонтали за одну единицу времени. Некие клеточки владеют иммунитетом, заразить их невероятно и через их не распространяются вирусы. Нужно написать программу, которая определяет мало возможное число вирусов, с подмогою которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток).
Описание входных данныхВ первой строке входного файла input.txt записаны два естественных числа n и m -размеры таблицы (количество строк и столбцов соответственно). Известно, что 1 n, m 100. Во 2-ой строке сначала записано одно число 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
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 gt; xmax then x:= xmax;
if x lt; xmin then x:= xmin;
if y gt; ymax then y:= ymax;
if y lt; 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 gt; 0 then
begin
t:= StartAkula;
if tlt;gt;nil then
repeat
d:= sqrt((x - t.x)*(x - t.x) + (y - t.y)*(y - t.y));
if d lt; opisanie[tip].See then
begin
if d lt; 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 lt; opisanie[tip].See then dx:= dx + 1/((x - xmin + eps)*strahkraj);
if xmax - x lt; opisanie[tip].See then dx:= dx + 1/((x - xmax - eps)*strahkraj);
if y - ymin lt; opisanie[tip].See then dy:= dy + 1/((y - ymin + eps)*strahkraj);
if ymax - y lt; opisanie[tip].See then dy:= dy + 1/((y - ymax - eps)*strahkraj);
d:= sqrt(dx*dx + dy*dy);
if d lt; 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
-
Вопросы ответы
Статьи
Информатика
Статьи
Математика.
Физика.
Математика.
Разные вопросы.
Разные вопросы.
Математика.
Разные вопросы.
Математика.
Физика.
Геометрия.