Найти минимальное число вирусов с помощью которых можно заразить прямоугольную область

@Nastya2019 · Регистрация: 23.11.2019

Студворк — интернет-сервис помощи студентам

Здравствуйте, мне нужен совет по задаче:
Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. Некоторые клетки обладают иммунитетом, заразить их невозможно и через них не распространяются вирусы. Напишите программу, которая найдёт минимально возможное число вирусов, с помощью которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток).

Входные данные
В первой строке входного файла 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
4 5
3 1 3 2 1 2 2
OUTPUT.TXT
2
Никак не могу сделать в две строки массив, чтобы он заполнил матрицу
Да и само задание сложновато для меня(
Буду рада всем ответам

@Anioni13 · 07.01.2020, 19:15

Ну изначально создаём массив (двумерный) и заполняем нулями

C++
1
2
3
4
5
6
7
8
 int s[n][m];
for (int i =0;i<n;i++)
{
for (int l =0;l<m;l++)
{
s[i][l]=0;
}
}

Добавлено через 11 минут
Изначально разберёмся по этому коду:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var
 n, m, i, j, k, l, i1, j1 : integer;
 a : array [0..101,0..101] of integer;
 t : boolean;
begin
 assign(input, 'input.txt'); reset(input);
 assign(output, 'output.txt'); rewrite(output);
 read(n,m,k);
 for i:=1 to n do for j:=1 to m do a[i,j]:=0;
 for i:=1 to n do begin a[i,0]:=0; a[i,m+1]:=-1 end;
 for j:=1 to m do begin a[0,j]:=0; a[n+1,j]:=-1 end;
 for l:=1 to k do begin read(i,j); a[i,j]:=-1 end;
 l:=0;
 for i:=1 to n do for j:=1 to m do
 if a[i,j]=0 then begin
 l:=l+1; a[i,j]:=l; t:=true;
 while t do begin
 t:=false;
 for i1:=1 to n do for j1:=1 to m do begin
 if (a[i1+1,j1]=l)and(a[i1,j1]=0) then begin t:=true;
a[i1,j1]:=l end;
 if (a[i1-1,j1]=l)and(a[i1,j1]=0) then begin t:=true;
a[i1,j1]:=l end;
 if (a[i1,j1+1]=l)and(a[i1,j1]=0) then begin t:=true;
a[i1,j1]:=l end;
 if (a[i1,j1-1]=l)and(a[i1,j1]=0) then begin t:=true;
a[i1,j1]:=l end;
 end
 end;
 end;
 write(l);
 close(output)
end.

@Nastya2019 · 08.01.2020, 01:19 **[ТС]**

Спасибо за ваш ответ
Я находила этот код, но разобраться так и не смогла (

@Nastya2019 · 08.01.2020, 16:17 **[ТС]**

А вы не могли бы рассказать про дальнейшие действия алгоритма?

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

@Nastya2019 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 4

	Найти минимальное число вирусов с помощью которых можно заразить прямоугольную область 07.01.2020, 18:47. Показов 4221. Ответов 3 Метки python, двумерный массив, заражение, клетки, матрица, с++ (Все метки) Здравствуйте, мне нужен совет по задаче: Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. Некоторые клетки обладают иммунитетом, заразить их невозможно и через них не распространяются вирусы. Напишите программу, которая найдёт минимально возможное число вирусов, с помощью которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток). Входные данные В первой строке входного файла 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 4 5 3 1 3 2 1 2 2 OUTPUT.TXT 2 Никак не могу сделать в две строки массив, чтобы он заполнил матрицу Да и само задание сложновато для меня( Буду рада всем ответам 0

@Nastya2019 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 4
	08.01.2020, 01:19 [ТС]
	Спасибо за ваш ответ Я находила этот код, но разобраться так и не смогла ( 0

@Nastya2019 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 4
	08.01.2020, 16:17 [ТС]
	А вы не могли бы рассказать про дальнейшие действия алгоритма? 0